When TM takes a snapshot, it has to find all the files that have changed since the last backup. To see if a file has changed, it just compares metadata (existence, date the data was last modified, date the metadata was last modified, etc.) for the file on the source disk and the file at the same path within the latest good snapshot.
But you have millions of files. Even if it only takes a millisecond to check a file, millions of milliseconds adds up to a long time. TM tries very hard not to have to examine every file.
To do that, it relies heavily on a part of the system called the File System Event Manager (FSEvent for short). A "file system event" is anything that an application that wants to know about changes might find interesting. Examples of such applications are Time Machine (so it can back up changed files) and Spotlight (so it can index them). Examples of noteworthy changes are: a program has closed a file after writing to it, a file has been created/deleted, a file or folder has been renamed or moved to another location.
The FSEvent manager can broadcast these events to systems that need to respond in real time, such as Spotlight. In OS X 10.5 Leopard, FSEvent manager started logging these events, so applications like TM that aren't running all the time can ask "What changed since ...?". To keep the log down to a manageable size, the FSEvent log doesn't record what file changed; rather, it records what folder the file was in. To further reduce the the log size, multiple changes to the same folder are coalesced. For example, moving 7 files from one folder to another is 14 events (each file was removed from the first folder, each file was added to the other folder), but logged as only two events (the two folders changed).
Even such vague information is good enough to help TM. When it takes a snapshot, it gets from FSEvent a list of the folders where there are changes, and compares the files/folder inside just those folders. That's enough to reduce the number of files it has to consider from millions down to thousands. Millions of milliseconds is a long time; thousands of milliseconds is manageable.
Except if there is a problem with the FSEvent log. There are things that can happen that make the FSEvent manager mistrust its log. For example, if the disk is not properly unmounted, or if you power off your computer without properly shutting down, or you have a kernel panic. When that happens, the old FSEvent log is deleted, and a new one is started.
The first time TM comes along after the FSEvent log has been restarted like this, and asks "What happened since my last snapshot?", the FSEvent manager replies "Beats me. My log doesn't go back that far in time. You're on your own." In that case, TM has no recourse but to spend the millions of milliseconds it takes to examine each and every one of the millions of files on your disk. This is called a "deep scan", and reported as such in the Console log.
While TM is determining which files need to be backed up, it displays its status as "preparing files". If it's in this state for a long time, it's probably doing a deep scan. (Or it could be deleting old snapshots to make room, which also counts as "preparing files". Looking in Console will tell you whether it's deleting old snapshots. It helps to enter "backupd" in Console's search field to limit output to just TM's messages.)
Once TM is able to make a good snapshot, future snapshots will be very fast until the next time FSEvent has to start a new log. If you want to keep TM speedy, avoid things that kill the FSEvent log.
As a matter of terminology: TM does not "index" files. Indexing files is something Spotlight does. TM will notice if Spotlight is indexing your backup volume, and will wait until Spotlight finishes. Otherwise, they get in each other's way, which would slow them both down dramatically. Things that make FSEvent mistrust its log files also tend to make Spotlight mistrust its database, causing it to re-index the entire volume. Re-indexing an entire volume can take a long time.
