As for the filesystem, ReiserFS on Linux is supposed to handle that kind of directly smoothly. However ext will slow to a crawl, and NTFS appears to as well.

The problem, of course, is that every mention of a file requires scanning the list of things in the directory, which means that you scan a list of many thousands of files many thousands of times. Unless the filesystem is designed for that, you have a problem.

Recommended solutions? Hierarchical structures (which is what most filesystems are designed to do), a dbm, a