filesystem for millions of small files

In terms of random seeks Reiser wins, followed by EXT4, followed by JFS. I'm not sure if this will correlate exactly to directory lookups, but it seems like it would be an indicator. You'll have to do your own tests for that specifically. EXT2 beats the pants off everything for file creation times, likely due to its lack of a journal, still EXT4 beats everything except Reiser which you may not want to use due to hans reiser's current status.

You might want to look into drives that support NCQ, and make sure your install is setup to use it. Under heavy seeking it should provide a speed boost.

Lastly, make sure your machine has a ton of ram. Since the files aren't often updated, linux will end up caching most of them to ram if it's got free space. If your usage patterns are right, this will give you a massive speed boost.

I agree with most of what Andrew said, except that I would recommend Reiser4 or the older (but better supported) ReiserFS. As those tests (and the documentation for ReiserFS) indicate, it is designed for precicesly the situation you are asking about (large numbers of small files or directories). I have used ReiserFS in the past with Gentoo and Ubuntu without any problems.

As to the status of Hans Reiser, I do not see it as being a problem with the code or stability of the File System itself. Reiser4 is even sponsored by both DARPA and Linspire so while I agree that the further development of the Reiser File System is undetermined, I do not thing that should be a deciding factor as to whether anyone should use it or not.

I know this is not a direct answer to your question, but in these cases I think a database might be more suitable to host this. Small files can be stored in binary format in a database table and retrieved at wil. The software that is using these files should be able to support this though...

Somebody over on the Unix StackExchange created a benchmark (with source) to test just this scenario:

Q: What is the most high-performance Linux filesystem for storing a lot of small files (HDD, not SSD)?

The best read performance seems to come from ReiserFS.