WikiDer > HTree
 | эта статья слишком полагается на использованная литература к основные источники. (Сентябрь 2013) (Узнайте, как и когда удалить этот шаблон сообщения) |
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]
использованная литература
- ^ Минмин Цао. «Индексирование каталога». Возможности Linux 2.6.
- ^ [email protected]. "Добавить поддержку индексированного каталога ext3 (htree)".
- ^ http://phunq.net/pipermail/tux3/2013-January/000026.html[ненадежный источник?]
- ^ «Архивная копия». Архивировано из оригинал на 2015-01-13. Получено 2014-12-28.CS1 maint: заархивированная копия как заголовок (ссылка на сайт)