HTree является специализированной древовидной структурой данных для индексирования каталога, похожей на B-дерево . Они имеют постоянную глубину одного или двух уровней, имеют высокий коэффициент разветвления, используют хэш имени файла и не требуют балансировки . [1] Алгоритм HTree отличается от стандартных методов B-дерева обработкой хеш-коллизий , которые могут переполняться по нескольким листовым и индексным блокам. Индексы HTree используются в файловых системах Linux ext3 и ext4 и были включены в ядро Linux. около 2.5.40. [2] Индексирование HTree улучшило масштабируемость файловых систем Linux на основе ext2 с практического ограничения в несколько тысяч файлов до десятков миллионов файлов на каталог.
История
Структура данных индекса HTree и алгоритм были разработаны Дэниелом Филлипсом в 2000 году и реализованы для файловой системы ext2 в феврале 2001 года. Порт на файловую систему ext3, сделанный Кристофером Ли и Эндрю Мортоном в 2002 году во время серии ядер 2.5, добавил согласованность сбоев на основе журналов . С небольшими улучшениями HTree продолжает использоваться в ext4 в серии ядра Linux 3.xx.
Использовать
- ext2 Индексы HTree изначально были разработаны для ext2, но патч так и не попал в официальную ветку. Функцию dir_index можно включить при создании файловой системы ext2, но код ext2 не будет работать с ней.
- Индексы ext3 HTree доступны в ext3, когда включена функция dir_index.
- Индексы ext4 HTree по умолчанию включены в ext4. Эта функция реализована в ядре Linux 2.6.23. Индексы HTree также используются для файловых экстентов, когда файлу требуется более 4 экстентов, хранящихся в inode .
PHTree
PHTree (физически стабильный HTree) является производным, задуманным как преемник. [3] Он устраняет все известные проблемы с HTree, кроме умножения записи. [ необходима цитата ] Он используется в файловой системе Tux3 . [4]
Рекомендации
- ^ Минмин Цао. «Индексирование каталога» . Возможности Linux 2.6 .
- ^ [email protected]. "Добавить поддержку индексированного каталога ext3 (htree)" .
- ^ http://phunq.net/pipermail/tux3/2013-January/000026.html [ ненадежный источник? ]
- ^ «Архивная копия» . Архивировано из оригинала на 2015-01-13 . Проверено 28 декабря 2014 .CS1 maint: заархивированная копия как заголовок ( ссылка )