For me the database rebuild happens on every boot (NW-A55), no matter whether a file changed it not. It's the one thing that constantly annoys me with this device as it takes several minutes...
AFAIK database rebuild is two steps; first is fsck_msdos, second is checking every file for changes. You can check the logs yourself by installing Wampy and enabling adb, maybe your filesystem is also having issues?