Три
-
Описание HTree
- HTree — специализированная древовидная структура данных для индексации каталогов.
- Имеет постоянную глубину в один или два уровня, высокий коэффициент разветвления.
- Использует хэш имени файла и не требует балансировки.
- Отличается от B-дерева обработкой коллизий хэшей.
-
История и использование
- Разработана Дэниелом Филлипсом в 2000 году.
- Реализована для ext2 в феврале 2001 года.
- Перенесена в ext3 в 2002 году, добавлена согласованность сбоев на основе журналов.
- Используется в ext4 с небольшими улучшениями.
-
Функции и реализация
- Индексы HTree ext2 не включены в официальную ветку.
- Функция dir_index доступна в ext3 при включении.
- Индексы HTree ext4 включены по умолчанию.
- Функция large_dir реализована в ext4 в ядре Linux 4.13.
-
PHTree
- PHTree (физически стабильное HTree) — производная, предназначенная как преемник.
- Устранены все известные проблемы с HTree, кроме умножения при записи.
- Используется в файловой системе Tux3.