Programming :: Scaling Of Directory Entry Lookup?

I need to create and access a very large number of directories (and by large I mean millions). Each directory's name consists only of numbers, which are incremented every time a new directory is created (so there will be directory 1, 2, and so on).Of course I could just dump all these directories under the same parent directory, but I reckon I would run into filesystem limits. Moreover, I presume that entry lookup is not a O(1) operation, which means that lookup does not scale well.

One solution is to use some sort of prefix tree for storing the data. In this scheme, the data for directory "1234" would actually be stored in "/1/2/3/4".This solution has the advantage that each subtree never has more than 10 entries, but the disadvantage of requiring as many individual lookups as the length of the path.There are also intermediate solutions: using a maximum of 100 entries per directory, "1234" would become "/12/34", per example.In order to choose the best scheme, I must know more about the scalability of directory lookup under Linux. What's the maximum reasonable number of entries for a directory before lookup becomes too slow? Does someone know exactly what are the limitations of the algorithm used for directory lookup?