HTre

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

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.[1] 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[rediger | rediger kilde]

  1. ^ Mingming Cao. «Directory indexing». Features found in Linux 2.6. 
informatikkstubbDenne informatikkrelaterte artikkelen er foreløpig kort eller mangelfull, og du kan hjelpe Wikipedia ved å utvide den.