One billion files on Linux

One thing you can do (and upstream, tools like rm do this now) is to get a bunch of entries back from readdir and then sort them by inode number.

That removes the random, seeky nature of the list for file systems that suffer from this (ext3/4, reiserfs, other?).

For the more advanced layouts, you should look to btrfs.