R-tree

Piccolo esempio di R-Tree per rettangoli 2d
Visualizzazione di un R*-Tree per cubi 3D

Gli R-tree o R-alberi sono un tipo di albero (grafo) simile al B-Albero, ma sono usati per indicizzare spazi multidimensionali, ad esempio le coordinate spaziali (X, Y) per dati geografici. Una richiesta di esempio che usi un R-tree potrebbe essere "Trova tutti i musei entro 2 km dalla mia posizione attuale".

La struttura dati divide lo spazio in MBR (minimum bounding rectangles, infatti R-tree deriva proprio da Rectangle) innestati gerarchicamente e quando possibile sovrapposti.

Ogni nodo dell'R-tree ha un numero variabile di entry (fino ad un massimo predeterminato). Ogni entry che non sia un nodo foglia contiene due entità: una identifica il nodo figlio, l'altra l'MBR che contiene tutte le entry del nodo figlio.

L'algoritmo di inserimento e cancellazione di entry dagli MBR assicura che elementi "vicini" siano posizionati nello stesso posto (nodo foglia): un nuovo elemento andrà nel nodo foglia che richiede il minor numero di estensioni delle dimensioni dell'MBR).

Gli algoritmi di ricerca usano gli MBR per decidere se cercare o meno nel nodo figlio del nodo corrente. In questo modo la maggior parte dei nodi non viene esplorata dagli algoritmi. Per questo motivo, come per i B-tree, ciò rende gli R-tree adatti ai database, dove i nodi possono essere copiati in memoria solo quando necessario.

Diversi algoritmi possono essere usati per dividere i nodi quando diventano troppo estesi, ovvero quando vengono aggiunti in un nodo un numero di elementi che supera il limite prestabiito.

Gli R-tree non garantiscono una performance ottima di caso peggiore, ma in generale si comportano molto bene con dati reali. Per questo nel 2004 è stato sviluppato un nuovo algoritmo (Priority R-tree), che cerca di essere efficiente ed allo stesso tempo ottimo rispetto al caso peggiore.

En otros idiomas
čeština: R-strom
Deutsch: R-Baum
English: R-tree
español: Árbol-R
français: R-arbre
עברית: עץ R
hrvatski: R-stablo
日本語: R木
한국어: R 트리
polski: R-drzewo
português: Árvores R
српски / srpski: Р-стабло
українська: R-дерево
中文: R树