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

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. . .

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.

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.