Kiedy wybrać RB tree, B-Tree lub AVL tree?

Myślę, że drzewa B+ są dobrą strukturą danych kontenera ogólnego przeznaczenia, nawet w pamięci głównej. Nawet jeśli pamięć wirtualna nie stanowi problemu, często jest przyjazna dla pamięci podręcznej, a drzewa B+ są szczególnie dobre dla dostępu sekwencyjnego - taka sama wydajność asymptotyczna jak lista powiązana, ale z przyjaznością dla pamięci podręcznej zbliżoną do prostej tablicy. Wszystko to I O (log n) Szukaj, Wstaw i usuń.

B+ drzewa mają jednak problemy - takie jak przedmioty poruszające się w obrębie węzłów, gdy robisz wstawia/usuwa, unieważniając wskaźniki do tych elementów. Mam bibliotekę kontenerów, która wykonuje "konserwację kursora" - Kursory dołączają się do węzła liścia, do którego obecnie odwołują się w połączonej liście, więc mogą być naprawiane lub unieważniane automatycznie. Ponieważ rzadko jest więcej niż jeden lub dwa Kursory, działa dobrze - ale jest to dodatkowy kawałek pracy.

Inna sprawa, że drzewo B+ jest w zasadzie tylko tym. Myślę, że można rozebrać lub odtworzyć węzły bez liści w zależności od tego, czy są potrzebne, czy nie, ale dzięki węzłom drzewa binarnego zyskujesz o wiele większą elastyczność. Drzewo binarne może być konwertowane do listy połączonej i z powrotem bez kopiowania węzłów - po prostu zmieniasz wskaźniki, a następnie pamiętaj, że traktujesz je teraz jako inną strukturę danych. Między innymi oznacza to dość łatwe łączenie O (n) drzew - konwertuje oba drzewa na listy, Scala je, a następnie konwertuje z powrotem do drzewa.

Kolejną rzeczą jest alokacja pamięci i uwalnianie. W drzewo binarne, można to oddzielić od algorytmów-użytkownik może utworzyć węzeł, a następnie wywołać algorytm insert, a delete może wyodrębnić węzły(odłączyć je od drzewa, ale nie zwolnić pamięci). W B-tree lub B+-tree, to oczywiście nie działa-dane będą żyć w węźle wielu elementów. Pisanie metod insert, które "planują" operację bez modyfikowania węzłów, dopóki nie dowiedzą się, ile nowych węzłów jest potrzebnych i że można je przydzielić, jest wyzwaniem.

Red black vs. AVL? Nie wiem, czy to robi jakąś różnicę. Moja własna Biblioteka ma klasę "narzędzia" opartą na zasadach do manipulowania węzłami, z metodami podwójnie połączonych list, prostych drzew binarnych, drzew splay, Czerwono-Czarnych drzew i treapów, w tym różnych konwersji. Niektóre z tych metod zostały wdrożone tylko dlatego, że byłem znudzony w tym czy innym czasie. Nie jestem pewien, czy nawet testowałem metody treap. Powodem, dla którego wybrałem czerwono-czarne drzewa zamiast AVL, jest to, że osobiście lepiej rozumiem algorytmy - które to nie znaczy, że są prostsze, to tylko Fuks historii, że jestem bardziej zaznajomiony z nimi.

Jeszcze jedno-moje kontenery B+ tree opracowałem tylko jako eksperyment. To jeden z tych eksperymentów, które nigdy się nie zakończyły, ale nie zachęcałbym innych do powtarzania. Jeśli potrzebujesz tylko zamówionego kontenera, najlepszą odpowiedzią jest użycie tego, który dostarcza twoja istniejąca biblioteka - np. std:: map etc w C++. Moja biblioteka ewoluowała przez lata, zajęło to sporo czasu, aby uzyskać jest stabilny, a ja niedawno odkryłem, że jest technicznie nie przenośny(zależy od trochę nieokreślonego zachowania WRT offsetof).

W pamięci B-Tree ma tę zaletę, że liczba elementów jest większa niż 32000... Spójrz na speedtest.pdf from stx-btree .

Wybierając struktury danych wymieniasz takie czynniki jak

• prędkość pobierania V prędkość aktualizacji
• Jak dobrze struktura radzi sobie z operacjami o najgorszym przypadku, na przykład wstawianiem rekordów, które docierają w uporządkowanej kolejności
• przestrzeń zmarnowana

Zacznę od przeczytania artykułów Wikipedii, do których odwołuje się Robert Harvey.

Pragmatycznie, pracując w językach takich jak Java Przeciętny programista ma tendencję do używania klas kolekcji pod warunkiem. Jeśli w ćwiczeniu dostrajania wydajności okaże się, że wydajność kolekcji jest problematyczna, można szukać alternatywnych implementacji. Rzadko jest to pierwsza rzecz, którą rozwój prowadzony przez firmę musi wziąć pod uwagę. Niezwykle rzadko zdarza się, że trzeba ręcznie implementować takie struktury danych, zwykle są biblioteki, z których można korzystać.