HTree - HTree

Nesmí být zaměňována s H strom, rodina fraktálních sad.

An HTree je specialista stromová datová struktura pro indexování adresářů, podobné a B-strom. Jsou to konstantní hloubka jedné nebo dvou úrovní, mají vysoký faktor rozdělování, použijte a hash z název souboru a nevyžadují vyvažování.[1] Algoritmus HTree se odlišuje od standardních metod B-stromu zpracováním hashovací kolize, které mohou přetékat přes více listových a indexových bloků. HTree indexy se používají v ext3 a ext4 Linux souborové systémy, a byly začleněny do Linuxové jádro kolem 2.5.40.[2] HTree indexování zlepšilo škálovatelnost Linux souborové systémy založené na ext2 od praktického limitu několika tisíc souborů do rozsahu 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 2.5 jádro série přidána časopis konzistence založená na selhání. S drobnými vylepšeními se HTree nadále používá v ext4 v řadě jádra Linux 3.x.x.

Použití

  • ext2 HTree indexy 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 fungovat.
  • ext3 Indexy HTree jsou k dispozici v ext3, když je povolena funkce dir_index.
  • ext4 Indexy HTree jsou ve výchozím nastavení v ext4 zapnuty. Tato funkce je implementována v linuxovém jádře 2.6.23. HTree indexy se také používají pro soubor rozsahy když soubor potřebuje více než 4 rozsahy uložené v souboru inode.

PHTree

PHTree (Fyzicky stabilní HTree) je derivace určená jako nástupce.[3] Opravuje všechny známé problémy s HTree kromě násobení zápisu.[Citace je zapotřebí ] Používá se v Tux3 souborový systém.[4]

Reference

  1. ^ Mingming Cao. "Indexování adresářů". Funkce nalezené v Linuxu 2.6.
  2. ^ [email protected]. "Přidat podporu indexovaného adresáře ext3 (htree)".
  3. ^ http://phunq.net/pipermail/tux3/2013-January/000026.html[nespolehlivý zdroj? ]
  4. ^ „Archivovaná kopie“. Archivovány od originál dne 2015-01-13. Citováno 2014-12-28.CS1 maint: archivovaná kopie jako titul (odkaz)

externí odkazy