It will rescan all of the folders. For each file found, it will check to see if it's in the database, and if it has been modified since the last time it was scanned. If it is new or has been modified, it will be loaded into memory to search for ID3 tags. This is the time consuming step. On my test syustem, with 500 songs, the first scan takes about 30 seconds or so; on the next startup, the rescan takes about half a second.
If none of the files are new, and all it has to do is confirm file locations, it can get through very fast. Make sure you are loading SMARTDRV in your AUTOEXEC.BAT; it'll speed up the indexing process.
--Chris