HTree - HTree
En HTree er en specialiseret træ datastruktur til biblioteket indeksering, der ligner et B-træ . De har konstant dybde på et eller to niveauer, har en høj fanout-faktor, bruger en hash af filnavnet og kræver ikke afbalancering . HTree-algoritmen adskiller sig fra standard B-træmetoder ved dens behandling af hashkollisioner , som kan løbe over flere blade og indeksblokke. HTree- indekser bruges i ext3- og ext4 Linux- filsystemerne og blev indarbejdet i Linux-kernen omkring 2.5.40. HTree-indeksering forbedrede skalerbarheden af Linux ext2-baserede filsystemer fra en praktisk grænse på et par tusinde filer i intervallet på titusindvis af filer pr. Bibliotek.
Historie
HTree-indeksets datastruktur og algoritme blev udviklet af Daniel Phillips i 2000 og implementeret til ext2-filsystemet i februar 2001. En port til ext3-filsystemet af Christopher Li og Andrew Morton i 2002 under 2.5- kerne- serien tilføjede journalbaseret crash-konsistens. Med mindre forbedringer fortsætter HTree med at blive brugt i ext4 i Linux 3.xx kerneserien.
Brug
- ext2 HTree-indekser blev oprindeligt udviklet til ext2, men patch'en kom aldrig til den officielle filial. Dir_index-funktionen kan aktiveres, når du opretter et ext2-filsystem, men ext2-koden fungerer ikke på det.
- ext3 HTree-indekser er tilgængelige i ext3, når dir_index-funktionen er aktiveret.
- ext4 HTree-indekser er som standard slået til i ext4. Denne funktion er implementeret i Linux-kerne 2.6.23. HTree-indekser bruges også til filudvidelser, når en fil har brug for mere end de 4 udvidelser, der er gemt i inoden .
PHTree
PHTree (fysisk stabil HTree) er en afledning beregnet som en efterfølger. Det løser alle de kendte problemer med HTree undtagen skrivemultiplikation. Det bruges i Tux3- filsystemet.
