HTre

HTre er en datastruktur for trær som brukes til indeksering av kataloger, på en lignende måte som B-trær. Det har en konstant dybde på enten et eller to nivåer, har en høy fan-out faktor, benytter hashtabeller til filnavnet, og er selvbalanserende. HTre-algoritmen skiller seg fra vanlige B-tre metoder ved sin behandling av kollisjoner som kallers kan gi overflyt langs flere løvnoder og indeksblokker. Htre-indekser ble tidligere benyttet i filsystemet ext3, og benyttes idag av ext4. Førstnevnte ble innlemmet i versjon 2.4.15 av Linuxkjernen, mens det sistnevnte ble innlemmet i versjon 2.6.28. Htre-indeksering øker skalerbarheten fra en praktisk grense på noen få tusen filer i ext2 til titalls millioner av filer per filkatalog.

Referanser

Kategori:Trær (datastrukturer)