HTree
HTree jest wyspecjalizowaną drzewiastą strukturą danych do indeksowania katalogów, podobną do B-drzewa . Mają stałą głębokość jednego lub dwóch poziomów, mają wysoki współczynnik fanout, używają skrótu nazwy pliku i nie wymagają równoważenia . Algorytm HTree różni się od standardowych metod B-drzewa traktowaniem kolizji mieszania , które mogą przepełniać wiele bloków liści i indeksów. Indeksy HTree są używane w systemach Linux ext3 i ext4 systemów plików i zostały włączone do jądra Linuksa około 2.5.40. Indeksowanie HTree poprawiło skalowalność Linuksie ext2 z praktycznego limitu kilku tysięcy plików do zakresu dziesiątek milionów plików w katalogu.
Historia
Struktura danych i algorytm indeksu HTree zostały opracowane przez Daniela Phillipsa w 2000 r. I zaimplementowane w systemie plików ext2 w lutym 2001 r. Port do systemu plików ext3 autorstwa Christophera Li i Andrew Mortona w 2002 r. Podczas serii jądra 2.5 dodał spójność awarii opartą na dzienniku . Z niewielkimi ulepszeniami, HTree jest nadal używane w ext4 w serii jądra Linuksa 3.xx.
Używać
- ext2 HTree zostały pierwotnie opracowane dla ext2, ale łatka nigdy nie trafiła do oficjalnej gałęzi. Funkcję dir_index można włączyć podczas tworzenia systemu plików ext2, ale kod ext2 nie będzie na niej działał.
- ext3 Indeksy HTree są dostępne w ext3, gdy włączona jest funkcja dir_index.
- ext4 HTree są domyślnie włączone w ext4. Ta funkcja jest zaimplementowana w jądrze Linuksa 2.6.23. określania zakresów plików , gdy plik potrzebuje więcej niż 4 zakresy przechowywane w i-węźle . Funkcja large_dir ext4 jest zaimplementowana w jądrze Linuksa 4.13.
PHTree
PHTree (Fizycznie stabilny HTree) to pochodna pomyślana jako następca. [ niewiarygodne źródło? ] Naprawia wszystkie znane problemy z HTree z wyjątkiem mnożenia zapisu. [ potrzebne źródło ] Jest używany w systemie plików Tux3 .
Linki zewnętrzne
- Indeks katalogów dla Ext2 (który opisuje strukturę danych HTree)
- HTree
- HPDD Wiki - Projekt wysokiego poziomu katalogu równoległego