HTree
 |
HTree — это специализированная древовидная структура данных для индексации каталогов, аналогичная B-дереву . Они имеют постоянную глубину в один или два уровня, имеют высокий коэффициент разветвления, используют хеш имени файла и не требуют балансировки . [ 1 ] Алгоритм HTree отличается от стандартных методов B-дерева тем, что он обрабатывает коллизии хэшей , которые могут переполняться в нескольких листовых и индексных блоках. HTree Индексы используются в ext3 и ext4 Linux файловых системах и были включены в ядро 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 экстентов, хранящихся в индексном дескрипторе . Функция big_dir ext4 реализована в ядре Linux 4.13.
PHTree
[ редактировать ]PHTree (Физически стабильный HTree) — это производная версия, задуманная как преемник. [ 3 ] [ ненадежный источник? ] Он исправляет все известные проблемы с HTree, за исключением умножения записи. [ нужна ссылка ] Он используется в файловой системе Tux3 . [ 4 ]
Ссылки
[ редактировать ]- ^ Минмин Цао. «Индексация каталога» (PDF) . Возможности, имеющиеся в Linux 2.6 .
- ^ [электронная почта защищена] . «Добавить поддержку индексированного каталога ext3 (htree)» .
- ^ «Обновление дизайна PHTree» . 4 января 2013 г.
- ^ «Файловая система управления версиями Tux3» . Архивировано из оригинала 13 января 2015 года . Проверено 28 декабря 2014 г.