B Albero rispetto ad un albero R - Non è solo un insieme di liste collegate collegate tra loro?

Un albero R può essere pensato come generalizzazione di un albero b. Laddove un albero b fornisce accesso O (log n) su un "raggio limitato" delle chiavi in esso contenute, un R Tree fornisce l'accesso O (log n) su una "K dimensional region" delle chiavi che contiene.

Se si desidera mappare i codici postali ai nomi delle province, è possibile utilizzare un B-Tree, dal momento che si potrebbe chiedere "Quali sono tutte le contee con codici di avviamento postale tra 60000 e 61000?" Tuttavia, un B-Tree non sarebbe adatto per mappare le coordinate GPS ai nomi delle province per domande come "Quali sono tutte le contee entro 100 miglia da Chicago?", Poiché ordina solo le sue chiavi su una singola dimensione. Un R-Tree rompe le sue chiavi in base a caselle di delimitazione sovrapposte, quindi è un modo naturale per archiviare le chiavi quando è necessario eseguire una query su più dimensioni.

La maggior parte delle strutture ad albero può essere ridotta a una qualche forma di elenco collegato, purché si ignori come viene costruito l'elenco (in particolare, come gli elementi vengono aggiunti e rimossi e come i nodi vengono ribilanciati, se applicabile). È essenzialmente l'algoritmo di inserimento / cancellazione / recupero che distingue una struttura dati da un'altra.

I nodi in un albero R in genere contengono un riquadro di delimitazione, che consente di indicizzare in modo efficiente le posizioni, come potrebbe essere necessario se si desidera cercare i record "vicino" a una determinata posizione. Gli elementi in un albero B hanno un ordinamento più semplice; puoi confrontare direttamente se qualcosa è maggiore o uguale a un altro elemento. In un R-Tree, lo scopo di ogni voce è determinare quali elementi sono contenuti in un riquadro di delimitazione.

Un B-Tree consente di cercare in modo efficiente elementi ordinabili nella memoria secondaria (come un disco rigido) e un R-Tree consente di cercare in modo efficiente elementi che si trovano "in" o "vicino" a un punto particolare oa un limite box, anche nella memoria secondaria.