Którą strukturę danych najlepiej użyć do organizacji plików? Czy B-Drzewa są najlepsze, czy istnieje inna struktura danych, która zapewnia szybszy dostęp do plików i dobrą organizację? DziękiStruktury danych używane do budowy systemów plików?
Wszystkie systemy plików są różne, więc istnieje ogromna liczba struktur danych, które faktycznie są używane w systemach plików.
Wiele systemów plików używa pewnego rodzaju bit vector (zwykle określanych jako mapa bitowa) do śledzenia lokalizacji niektórych wolnych bloków, ponieważ mają one doskonałą wydajność do sprawdzania, czy określony blok dysku jest używany i (dla dysków, które nie są używane). "w przeważającej mierze pełna") obsługuje dość szybkie wyszukiwanie wolnych bloków.
Wiele starszych systemów plików (ext i ext2) zapisało struktury katalogów przy użyciu prostych połączonych list. Najwyraźniej było to wystarczająco szybkie dla większości aplikacji, chociaż niektóre typy aplikacji, które używały wielu dużych katalogów, odniosły zauważalne hity wydajności.
System plików XFS słynął z tego, że używa niemalże wszystkiego, łącznie ze strukturami katalogów i systemem księgowania. Z tego, co pamiętam z mojego undergradowego kursu OS, wynikało, że skoro tak długo trwało pisanie, debugowanie i wydajność, aby dostroić implementację klasy B +, to sensownym było użycie jej w jak największym stopniu.
Inne systemy plików (ext3 i ext4) używają wariantu drzewa B nazywanego HTree, którego nie znam. Wygląda na to, że używa jakiegoś schematu mieszania, aby utrzymać współczynnik rozgałęzienia na wysokim poziomie, tak że używa się bardzo niewielu dostępów do dysku.
Słyszałem anegdotycznie, że niektóre systemy operacyjne próbowały używać splay trees do przechowywania struktur katalogów, ale napotkały na problemy z nimi. W szczególności uniemożliwiło to wielowątkowy dostęp do tego samego katalogu z wielu czytników (ponieważ w drzewie odtwarzania każdy dostęp zmienia kształt drzewa) i napotkał przypadek krawędzi, w którym drzewo ulegałoby degeneracji do listy połączonej, jeśli wszystkie elementy drzewa byłyby uzyskiwane sekwencyjnie. Powiedział, że nie wiem, czy to tylko miejska legenda, ponieważ te problemy byłyby widoczne, zanim ktokolwiek spróbowałby je zakodować.
System FAT32 firmy Microsoft używał ogromnej tablicy (tabeli alokacji plików), w której przechowywane są przechowywane pliki, a które sektory dysków następują logicznie w pliku. Główną wadą jest to, że stół musiał zostać wcześniej skonfigurowany, więc kończyły się górne limity rozmiarów plików, które można przechowywać na dysku. Jednak system oparty na tablicach był dość łatwy do wdrożenia.
To nie jest wyczerpująca lista - jestem pewien, że inne systemy plików używają innych struktur danych. Mam jednak nadzieję, że pomoże ci to we właściwym kierunku.
Mam nadzieję, że to pomoże!
Bardzo przydatny post dziękuję! Zbadam wtedy wektory bitowe i zrobię trochę więcej badań na temat innych systemów operacyjnych. Słyszałem, że drzewa gry były niepokojące! Jestem zaznajomiony z B-Drzewami, ale nie mogę się doczekać nauki innych struktur danych, które będą przydatne w tego typu sprawach! Dzięki za twoją długą odpowiedź :) – Bernice
Jestem fanem używania baz danych do przechowywania informacji. Uważam, że większość DB używa struktury b. Czy istnieje konkretne zadanie, które chcesz wykonać? – kevingreen
Po prostu ciekawi mnie struktura danych wykorzystywana przez OS do organizacji plików, ponieważ uczę się struktur danych i zaimplementowałem kilka z nich: Czerwone Czarne Drzewa, Drzewa AVL, B-Drzewa, Listy Pomiń ... Chciałbym wiem, które z nich mogę użyć do bardziej użytecznego zadania (nie zapisywania liczb). – Bernice
Nie jestem pewien, w jaki sposób większość OS przechowuje dane. Powodzenia w badaniach. – kevingreen