В вашем случае я бы ещё посмотрел в сторону баз данных.
Слишком много папок тоже плохо - чем больше вложенность, тем больше будет оверхэд по инодам. Всё зависит от файловой системы и от того, что вы понимаете под "очень много". По опыту скажу, что ext4 с множеством метаданных справляется быстрее остальных и скорее всего подойдёт для такой задачи, XFS наоборот хороша для хранения очень больших файлов - баз данных, например.
Есть ещё новая ФС - btrfs, она умеет держать метаданные для большой файловой системы на SSD дисках, а данные - на более медленных. Для больших хранилищ самое то.
Далее уже просто экспериментально можно проверить, что будет быстрее - большая вложенность или множество файлов в одной папке. Судя по структуре хранилища хабра наиболее оптимальным считается 4096 элементов на каталог.
events.linuxfoundation.org/slides/2010/linuxcon201...
См. также
Какое максимально число папок можно создавать в папке?