Базовая структура каталогов, используемая Ext4 (и Ext3 ), точно такая же, как в Ext2 . Ext3 добавляет ведение журнала, Ext4 улучшает это ведение журнала.Журналирование не имеет отношения к вашему вопросу.
Первоначально Ext2 использовался для хранения этого списка, но это, конечно, было неэффективно для больших каталогов.Так что это было изменено на улучшенную версию B-дерева под названием HTree .В отличие от стандартного B-дерева, HTree имеет постоянную глубину и использует хеш-карту для каждого узла, поэтому его сложность поиска составляет O (1) .
Схема Ext2, которую мы назвали «HTree», использует 32-битные хеш-коды для ключей, где каждый хеш-ключ ссылается на диапазон записей, хранящихся в листовом блоке.Поскольку внутренние узлы имеют только 8 байтов, HTree имеют очень высокий коэффициент разветвления (более 500 блоков могут ссылаться с помощью блока индекса 4K), двух уровней узлов индекса достаточно для поддержки более 16 миллионов имен файлов из 52 символов.Чтобы еще больше упростить реализацию, HTree имеют постоянную глубину (один или два уровня).Сочетание высокого коэффициента разветвления и использования хэша имени файла, а также секрета, специфичного для файловой системы, который служит в качестве ключа поиска для HTree, устраняет необходимость в реализации для выполнения операций балансировки.
См .: http://ext2.sourceforge.net/2005-ols/paper-html/node3.html