HTree - HTree

Не путать с H дерево, семейство фрактальных множеств.

An 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.x.x.

Использовать

  • ext2 Индексы HTree изначально были разработаны для ext2, но патч так и не попал в официальную ветку. Функцию dir_index можно включить при создании файловой системы ext2, но код ext2 не будет действовать на нее.
  • ext3 Индексы HTree доступны в ext3, если включена функция dir_index.
  • ext4 Индексы HTree по умолчанию включены в ext4. Эта функция реализована в ядре Linux 2.6.23. Индексы HTree также используются для файловых экстенты когда файлу требуется более 4 экстентов, хранящихся в индекс.

PHTree

PHTree (физически стабильный HTree) является производным, задуманным как преемник.[3] Он устраняет все известные проблемы с HTree, кроме умножения записи.[нужна цитата ] Он используется в Tux3 файловая система.[4]

использованная литература

  1. ^ Минмин Цао. «Индексирование каталога». Возможности Linux 2.6.
  2. ^ [email protected]. "Добавить поддержку индексированного каталога ext3 (htree)".
  3. ^ http://phunq.net/pipermail/tux3/2013-January/000026.html[ненадежный источник? ]
  4. ^ «Архивная копия». Архивировано из оригинал на 2015-01-13. Получено 2014-12-28.CS1 maint: заархивированная копия как заголовок (ссылка на сайт)

внешние ссылки