HTree
En HTree är en specialiserad träddatastruktur för katalogindexering, liknande ett B-träd . De har konstant djup på antingen en eller två nivåer, har en hög fanout-faktor, använder en hash av filnamnet och kräver inte balansering . HTree-algoritmen särskiljs från standard B-tree-metoder genom sin behandling av hashkollisioner , som kan svämma över över flera blad och indexblock. HTree- index används i Linux- filsystemen ext3 och ext4 , och inkorporerades i Linux-kärnan runt 2.5.40. HTree-indexering förbättrade skalbarheten hos Linux ext2-baserade filsystem från en praktisk gräns på några tusen filer till tiotals miljoner filer per katalog.
Historia
HTree-indexdatastrukturen och algoritmen utvecklades av Daniel Phillips 2000 och implementerades för ext2-filsystemet i februari 2001. En port till ext3-filsystemet av Christopher Li och Andrew Morton 2002 under 2.5- kärnserien lade till journalbaserad kraschkonsistens. Med mindre förbättringar fortsätter HTree att användas i ext4 i Linux 3.xx-kärnserien.
Använda sig av
- ext2 HTree-index utvecklades ursprungligen för ext2 men patchen kom aldrig till den officiella grenen. Dir_index-funktionen kan aktiveras när du skapar ett ext2-filsystem, men ext2-koden kommer inte att påverka det.
- ext3 HTree-index är tillgängliga i ext3 när dir_index-funktionen är aktiverad.
- ext4 HTree-index är aktiverade som standard i ext4. Den här funktionen är implementerad i Linux-kärnan 2.6.23. HTree-index används också för filomfattningar när en fil behöver mer än de 4 omfattningar som finns lagrade i inoden . Large_dir-funktionen i ext4 är implementerad i Linux-kärnan 4.13.
PHTree
PHTree (Physically stabil HTree) är en härledning avsedd som en efterföljare. [ opålitlig källa? ] Det fixar alla kända problem med HTree förutom skrivmultiplikation. [ citat behövs ] Den används i Tux3 -filsystemet.
externa länkar
- Ett katalogindex för Ext2 (som beskriver HTree-datastrukturen)
- HTree
- HPDD Wiki - Parallell Directory High Level Design