Árbol H

Este artículo se basa excesivamente en referencias a fuentes primarias . Por favor, mejore este artículo añadiendo fuentes secundarias o terciarias . Buscar fuentes:  «HTree» – noticias  · periódicos  · libros  · académico  · JSTOR ( septiembre de 2013 ) ( Aprenda cómo y cuándo eliminar este mensaje )

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.

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

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]

• Un índice de directorio para Ext2 (que describe la estructura de datos HTree)
• Árbol H
• Wiki HPDD: directorio paralelo de diseño de alto nivel