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?

I understand this question may be a bit too technical for this forum. If that is indeed the case, what would be the best place to put it instead?

Thanks in advance,
Jon

It depends on the filesystem. Have you already decided which one to use?

If you use ext4, you can use tune2fs to enable dir_index (hashed b-trees) to speed up lookup for large directories. I believe with ext4 and dir_index enabled a two-level design is probably optimal: say 1000 to 60000 subdirectories, and the files (or actual directories) roughly evenly distributed in the subdirectories. You should be fine with that to at least 360 million files/directories. Note that I don't think ext4 has any limits here; you could put them all in the same directory. (ls and shells would be pretty unhappy, though.)

If you intend to create a multi-terabyte filesystems, XFS is a better choice. I believe it behaves roughly the same.

I'd recommend reading the linux-fsdevel mailing list archives for details.