Drzewo B w porównaniu do drzewa R - Czy to nie tylko kilka połączonych ze sobą list?

10

Dość dobrze znam drzewo B, głównie dlatego, że muszę dobrze zaopatrywać bazy danych w energię elektryczną, klimatyzację i przestrzeń na dysku twardym. Kojarzy mi się z podwójnie połączoną listą (doubl [tj. Ey]?).

Dzisiaj jeden z programistów podczas lunchu wspomniał o drzewie R.

Wskoczyłem na Wikipedię i zacząłem czytać. Brzmiało to okropnie jak wyższe drzewo B. Niestety brak głębokiej wiedzy matematycznej utrudnia zrozumienie, o czym mówią niektórzy z moich współpracowników.

Miałem nadzieję, że ktoś może wyjaśnić kilka różnic między drzewem B i drzewem R. Prawdopodobnie i tak skończę z pytaniem, ale nie ma gwarancji, że odpowiedzą na moje pytanie. Bardziej niż prawdopodobne, że zaczną gadać o Bogu, wiedzą co. . .

surfasb
źródło
BTree zdecydowanie nie jest jak podwójnie połączona lista. Drzewo pozwala na dostęp do operacji log (n) zamiast proporcjonalnych do n, jak na listach.
Javier
@Javier: węzły liści indeksu b-drzewa są zwykle podwójnie połączoną listą, aby umożliwić szybkie pobieranie węzłów indeksu przez rodzeństwo.
Jordan
1
Jest to pytanie czysto techniczne, należy ono do StackOverflow (nie należy go jednak tam ponownie publikować, zostanie ono zautomatyzowane, jeśli wystarczająca liczba osób zagłosuje tutaj, aby je zamknąć).
Péter Török
1
To na ten temat tutaj: Programmers.SE służy do pytań koncepcyjnych dotyczących programowania. Przepełnienie stosu ma miejsce wtedy, gdy rzeczywiście masz kod, z którym potrzebujesz pomocy.
2
@Peter Torok: W starym systemie to MUSI być pytaniem SO. Ale teraz, gdy ta strona istnieje.
surfasb

Odpowiedzi:

7

Drzewo R można uznać za uogólnienie b-drzewa. Tam, gdzie b-drzewo zapewnia dostęp O (log n) w „ograniczonym zakresie” zawartych w nim kluczy, drzewo R zapewnia dostęp O (log n) przez „K wymiarowy obszar” zawartych w nim kluczy.

Jeśli chcesz zmapować kody pocztowe na nazwy hrabstw, możesz użyć drzewa B, ponieważ możesz zapytać: „Jakie są hrabstwa z kodami pocztowymi między 60000 a 61000?”. Jednak B-Tree nie nadawałby się do mapowania współrzędnych GPS do nazw hrabstw w przypadku zapytań takich jak „Jakie są hrabstwa w promieniu 100 mil od Chicago?”, Ponieważ zamawia klucze tylko w jednym wymiarze. Drzewo R rozbija klucze zgodnie z nakładającymi się ramkami ograniczającymi, dlatego jest to naturalny sposób przechowywania kluczy, gdy trzeba wykonać zapytanie dotyczące wielu wymiarów.

SingleNegationElimination
źródło
Podoba mi się ta analogia.
surfasb
1
Bardziej konkretny przykład niż analogia. Dokładnie tak są używane te algorytmy indeksowania.
SingleNegationElimination
6

Większość struktur drzewa można zredukować do jakiejś formy listy połączonej, o ile zignorujesz sposób tworzenia listy (w szczególności sposób dodawania i usuwania elementów oraz, w razie potrzeby, równoważenia węzłów). Zasadniczo jest to algorytm wstawiania / usuwania / wyszukiwania, który odróżnia jedną strukturę danych od drugiej.

Węzły w drzewie R zazwyczaj zawierają obwiednię, która pozwala skutecznie indeksować lokalizacje, co może być potrzebne, jeśli chcesz wyszukać rekordy „w pobliżu” określonej lokalizacji. Elementy w drzewie B mają prostszą kolejność; możesz bezpośrednio porównać, czy coś jest większe lub równe innemu elementowi. W drzewie R celem każdego wpisu jest określenie, które elementy są zawarte w obwiedni.

B-Tree pozwala efektywnie wyszukiwać elementy do zamówienia w pamięci dodatkowej (np. Na dysku twardym), a R-Tree pozwala efektywnie wyszukiwać elementy, które są „w” lub „w pobliżu” określonego punktu lub ramki granicznej, również w pamięci wtórnej.

JasonTrue
źródło
Wygląda na to, że drzewo R zaczyna się rozróżniać w miarę wzrostu liczby elementów, prawda? Czy jest to trochę zbyt uproszczone?
surfasb
Myślę, że biorąc pod uwagę podobną liczbę węzłów, nie zobaczyłbyś szczególnej różnicy w wykorzystaniu przestrzeni, z wyjątkiem kosztu liniowego danych ramki granicznej w węzłach innych niż liście. Ale po prostu nie możesz skutecznie reprezentować obwiedni w konwencjonalnej definicji B-drzewa, więc z pewnością użyłbyś dużo więcej miejsca, gdybyś próbował przedstawić informacje przestrzenne na B-drzewie. R-Tree służy do relacji przestrzennych, B-Tree obsługuje tylko porządkowanie jednowymiarowe.
JasonTrue
2
@JasonTrue: W rzeczywistości istnieją skuteczne sposoby na linearyzację obwiedni dla indeksowania B-Tree: en.wikipedia.org/wiki/Geohash . Chociaż skróty są „wydajne”, nie są szczególnie wygodne. Dowolne zapytanie ramki ograniczającej prawdopodobnie zajmie 9 oddzielnych zapytań dla przestrzeni 2-wymiarowej, a jeśli pole pokrywa się z główną osią (powiedzmy, międzynarodową linią danych), liczba zapytań może się podwoić lub poczwórnie i korzystanie z niego staje się bardzo kłopotliwe. Mimo to nadal jest to opcja, gdy indeksy liniowe są jedynym dostępnym rodzajem.
SingleNegationElimination