HTree - HTree
HTree je specializovaný stromová struktura dat pro adresáře indexování, podobně jako u B-stromu . Jsou konstantní hloubka jedné nebo dvou úrovních, mají vysokou fanout faktorem, pomocí hash ze souboru , a nevyžadují vyvažování . Algoritmus HTree se odlišuje od standardních metod B-stromu zpracováním kolizí hash , které mohou přetékat přes více listových a indexových bloků. HTree indexy jsou použity v ext3 a ext4 linuxových souborových systémů , a byl včleněn do linuxového jádra kolem 2.5.40. Indexování HTree zlepšilo škálovatelnost souborových systémů založených na systému Linux ext2 z praktického limitu několika tisíc souborů na rozsah desítek milionů souborů na adresář.
Dějiny
Datová struktura a algoritmus indexu HTree byly vyvinuty Danielem Phillipsem v roce 2000 a implementovány pro souborový systém ext2 v únoru 2001. Port do souborového systému ext3 Christopher Li a Andrew Morton v roce 2002 během série jádra 2.5 přidali konzistenci zhroucení deníku . S drobnými vylepšeními se HTree nadále používá v ext4 v řadě jádra Linux 3.xx.
Použití
- indexy ext2 HTree byly původně vyvinuty pro ext2, ale patch se nikdy nedostal do oficiální pobočky. Funkci dir_index lze povolit při vytváření souborového systému ext2, ale kód ext2 na ni nebude působit.
- indexy ext3 HTree jsou k dispozici v ext3, když je povolena funkce dir_index.
- ext4 HTree indexy jsou ve výchozím nastavení zapnuty v ext4. Tato funkce je implementována v linuxovém jádře 2.6.23. Indexy HTree se také používají pro rozsahy souborů, pokud soubor potřebuje více než 4 rozsahy uložené v inodu .
PHTree
PHTree (Fyzicky stabilní HTree) je derivace určená jako nástupce. Opravuje všechny známé problémy s HTree kromě násobení zápisu. Používá se v souborovém systému Tux3 .