Why are hard-links to directories that much faster? It seems like creating a bunch of actual directories with hard-linked files in them is a trivial difference. They still need to scan the files to figure out what has changed, and that's where the really time sink is, no?
Well, consider the case when nothing has changed. All they do is hard link the top level directory and they are done.
2011-06-12 -> 2011-06-13
On my Linux machine when I do rsync backups it has to create a new inode for each file in the new directory whether or not it has changed. Even on a moderately sized directory tree this can take an hour or more (you can benchmark yourself with "cp -al". Try copying your whole disk just for fun). Time machine completes a cycle in 10 minutes or so and that includes the new data copying.
For small amounts of files I agree with you that the hard linked directories would make a trivial difference. Keep in mind that by default Time Machine backs up /usr, /Applications and /System along with your user data which is quite a lot of files in the end.
That's all just creating the new backup's directory tree. The new data copying itself is fast because Time Machine uses the FSEvents API (which is like inotify but more suitable for backing up) so that it knows exactly what it has to back up beforehand (no scanning). If your computer crashes or you switch disks or otherwise screw up your FSEvents DB then it does have to scan the whole disk looking for changes and that can take hours.
So technically it is fast because it uses FSEvents and also because it can hard link directories. If either of those things are missing then the process would be significantly slower.
No. Time Machine uses the FSEvents API so that it only needs to scan directories where files have changed since the last backup, and branches of the filesystem hierarchy whose contents haven't changed can be referenced en masse with a single directory hard link to the previous backup; it's much faster than scanning or re-linking ~1M files and folders, and much more space-efficient (especially the way that hard links are implemented on HFS+).
