Сегодня сделал тесты разных файловых систем. Исходник вот здесь:
http://rsdn.ru/File/37054/benchmark.zip (для компиляции требуется версия
Boost из CVSа).

В тесте создается каталог с N файлами, а затем M раз выполняется stat()
и fopen/fclose, где N — первый параметр, M — второй параметр.

Вот результат с Reiser4:

root@prlinux:/tmp/benchmark# ./benchmark 1000 1000000
Starting files creation...
Finished files creation. Time:0.06
Timing 'stat'...
Finished timing:2.76, 1000000 iterations.
Timing open/close...
Finished timing:6.64, 1000000 iterations.
Starting files removing...
Finished files removing. Time:0.11

root@prlinux:/tmp/benchmark# ./benchmark 100000 1000000
Starting files creation...
Finished files creation. Time:6.26
Timing 'stat'...
Finished timing:3.61, 1000000 iterations.
Timing open/close...
Finished timing:7.61, 1000000 iterations.
Starting files removing...
Finished files removing. Time:11.63

root@prlinux:/tmp/benchmark# ./benchmark 300000 1000000
Starting files creation...
Finished files creation. Time:18.77
Timing 'stat'...
Finished timing:3.77, 1000000 iterations.
Timing open/close...
Finished timing:7.6, 1000000 iterations.
Starting files removing...
Finished files removing. Time:35.85

То есть видно, что элементы добавляются за O(1), а поиск идет за O(log
N) времени. То есть Reiser4 вполне себе подходит для больших объемов
данных, особенно если учитывать возможность построения custom'ных
индексов по хранимым файлам (в том числе и по содержанию). Скорость
работы тоже вполне приемлима.

В NTFS под Windows все намного хуже — видна работа маляра Шлэмиля (или
менее оптимальные алгоритмы работы с диском):

C:\temp\benchmark\bin\msvc\release>benchmark.exe 1000 1000000
Starting files creation...
Finished files creation. Time:0.31
Timing 'stat'...
Finished timing:12.338, 1000000 iterations.
Timing open/close...
Finished timing:25.146, 1000000 iterations.
Starting files removing...
Finished files removing. Time:0.14

C:\temp\benchmark\bin\msvc\release>benchmark.exe 10000 1000000
Starting files creation...
Finished files creation. Time:3.094
Timing 'stat'...
Finished timing:13.74, 1000000 iterations.
Timing open/close...
Finished timing:25.727, 1000000 iterations.
Starting files removing...
Finished files removing. Time:3.274

C:\temp\benchmark\bin\msvc\release>benchmark.exe 50000 1000000
Starting files creation...
Finished files creation. Time:31.064
Timing 'stat'...
Finished timing:23.714, 1000000 iterations.
Timing open/close...
Finished timing:35.842, 1000000 iterations.
Starting files removing...
Finished files removing. Time:12.468

При этом тестовая виндовая намного машина лучше линуксовой.