Árbol HT

Un HTree es una estructura de datos de árbol especializada para la indexación de directorios, similar a un árbol B. Tienen una profundidad constante de uno o dos niveles, un alto factor de fanout, utilizan un hash del nombre del archivo y no requieren balanceo . ^{[ 1 ]} El algoritmo HTree se distingue de los métodos estándar de árboles B por su tratamiento de las colisiones de hash , que pueden desbordarse a través de múltiples bloques de hojas e índices. Los índices HTree se utilizan en los sistemas de archivos Linux ext3 y ext4 , y se incorporaron al kernel de Linux alrededor de la versión 2.5.40. ^{[ 2 ]} La indexación HTree mejoró la escalabilidad de los sistemas de archivos Linux basados ​​en ext2 desde un límite práctico de unos pocos miles de archivos, hasta el rango de decenas de millones de archivos por directorio.

La estructura de datos y el algoritmo del índice HTree fueron desarrollados por Daniel Phillips en 2000 e implementados para el sistema de archivos ext2 en febrero de 2001. Una adaptación al sistema de archivos ext3 realizada por Christopher Li y Andrew Morton en 2002, durante la serie de kernels 2.5 , añadió consistencia de fallos basada en el registro de transacciones . Con pequeñas mejoras, HTree continúa utilizándose en ext4 en la serie de kernels Linux 3.xx.

• Los índices HTree de ext2 se desarrollaron originalmente para ext2, pero el parche nunca se incorporó a la rama oficial. La función dir_index se puede habilitar al crear un sistema de archivos ext2, pero el código de ext2 no la tendrá en cuenta.
• Los índices HTree de ext3 están disponibles en ext3 cuando la función dir_index está habilitada.
• Los índices HTree de ext4 están activados por defecto. Esta característica se implementó en el kernel de Linux 2.6.23. Los índices HTree también se utilizan para las extensiones de archivo cuando un archivo necesita más de las 4 extensiones almacenadas en el inodo . La función large_dir de ext4 se implementó en el kernel de Linux 4.13.

PHTree (HTree físicamente estable) es una derivación concebida como sucesora. ^{[ 3 ]} Corrige todos los problemas conocidos de HTree, excepto la multiplicación de escritura. Se utiliza en el sistema de archivos Tux3 . ^{[ 4 ]}

• Un índice de directorio para Ext2 (que describe la estructura de datos HTree)
• Árbol HT
• Wiki de HPDD - Diseño de alto nivel de directorios paralelos