Un HTree es una estructura de datos de árbol especializada para la indexación de directorios, similar a un B-tree . Tienen una profundidad constante de uno o dos niveles, tienen un alto factor de abanico de salida, utilizan un hash del nombre de archivo y no requieren balanceo . [1] El algoritmo HTree se distingue de los métodos estándar de B-tree por su tratamiento de las colisiones de hash , que pueden desbordarse en múltiples bloques de hoja e índice. Los índices HTree se utilizan en los sistemas de archivos ext3 y ext4 de Linux , y se incorporaron al kernel de Linux alrededor de 2.5.40. [2] La indexación HTree mejoró la escalabilidad de los sistemas de archivos basados en ext2 de Linux 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 de índice HTree fueron desarrollados por Daniel Phillips en 2000 e implementados para el sistema de archivos ext2 en febrero de 2001. Un puerto al sistema de archivos ext3 realizado por Christopher Li y Andrew Morton en 2002 durante la serie de kernels 2.5 agregó consistencia de errores basada en el diario . Con pequeñas mejoras, HTree continúa siendo utilizado en ext4 en la serie de kernels Linux 3.xx.
PHTree (HTree físicamente estable) es una derivación pensada como sucesora. [3] [ ¿ Fuente poco confiable? ] Corrige todos los problemas conocidos con HTree excepto la multiplicación de escritura. [ Cita requerida ] Se utiliza en el sistema de archivos Tux3 . [4]