C/C++: Jak przechowywać dane w pliku w drzewie B

Question

Wydaje mi się, że jeden sposób przechowywania danych w B-drzewie jako plik może być efektywnie wykonany przy pomocy C pliku binarnego z sekwencją (tablicą) struktur, przy czym każda struktura reprezentuje węzeł. W ten sposób można połączyć poszczególne węzły z podejściem, które będzie podobne do tworzenia list połączonych za pomocą tablic. Ale wtedy problem polegający na usunięciu węzła byłby usunięciem węzła, ponieważ wymazanie tylko kilku bajtów w środku ogromnego pliku nie jest możliwe.

Jednym ze sposobów usuwania może być śledzenie "pustych" węzłów do momentu osiągnięcia progowego odcięcia, a następnie utworzenie kolejnego pliku, który odrzuci puste węzły. Ale to jest nużące.

Czy istnieje lepsze podejście z punktu widzenia prostoty/wydajności do usuwania lub nawet reprezentowania drzewa B w pliku?

TIA, -Sviiya

Answer 1

Zrobiłem bardzo szybkie wyszukiwanie i wykopali to: http://people.csail.mit.edu/jaffer/WB C Źródło: http://cvs.savannah.gnu.org/viewvc/wb/wb/c/ - wydaje się oferować B-Tree stylu baz danych dyskowych - chociaż przyjrzeniu „usuń .c "wydawało się sugerować, że jeśli usuniesz węzeł, wszystko zostanie usunięte - jeśli to jest prawidłowe zachowanie, to brzmi jak coś, co może pomóc?

Również - B-drzewa są często używane w systemach plików - czy nie mógłbyś spojrzeć na jakiś kod systemu plików?

Moja własna inklinacja to system plików - jeśli masz drzewo B o stałym rozmiarze, za każdym razem, gdy "usuniesz" węzeł zamiast próbować usunąć odniesienie, po prostu ustaw wartość, co oznacza nic w twoim kodzie. Następnie uruchom wątek czyszczący, który sprawdza, czy ktoś ma otwarty plik do czytania, a jeśli wszystko jest w porządku, blokuje plik i porządkuje.

Answer 2

Możesz również użyć DB Berkley. Działa dobrze z programami C i implementuje drzewo B +.

Answer 3

Do implementacji B-drzew w pliku można użyć przesunięcia pliku zamiast wskaźników. Możesz także zaimplementować "menedżera pamięci plików", aby móc ponownie używać usuniętych elementów w pliku.

Aby w pełni odzyskać usunięte bloki w pliku B-Tree, konieczne będzie odtworzenie drzewa B w nowym pliku. Pamiętaj również, że większość systemów operacyjnych nie ma metod skracania plików. Przenośną metodą obcinania pliku jest napisanie nowego pliku i zniszczenie starego.

Inną propozycją jest podział pliku na partycję B-Tree i partycję danych (elementów). Partycja B-Tree będzie zawierała strony. Strony liści będą zawierały przesunięcia do elementów danych. Partycja danych będzie sekcją w pliku zawierającym elementy danych. Możliwe, że utworzysz więcej niż jedną partycję i partycje mogą być przeplatane.

Spędziłem dużo czasu, grając z opartym na plikach B-Tree, aż dałem sobie spokój i zdecydowałem się pozwolić, aby program bazy danych (lub serwer) obsługiwał dane dla mnie.