R-tree

Gli R-tree o R-alberi sono un tipo di albero 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".

Visualizzazione di un R*-Tree per cubi 3D

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.

Algoritmi

Ricerca

L'input è un rettangolo MBR. La ricerca è simile a quella dei B-tree. Essa parte dal nodo radice e si estende ad ogni nodo figlio (contenente sia rettangoli MBR che puntatori ai nodi figli). Giunti al nodo foglia si hanno i veri e propri oggetti multidimensionali. Per ogni MBR incontrato si verifica se esso è sovrapposto con il rettangolo di ricerca (di input) o meno. Se esso è sovrapposto si cerca anche in quel nodo corrispondente, altrimenti no. La ricerca procede quindi in un modo ricorsivo, fermandosi quando tutti gli MBR sovrapposti sono stati esplorati. Un oggetto viene aggiunto all'insieme di ricerca (l'output dell'algoritmo) quando si trova in un MBR che si sovrappone all'MBR query.

Aggiunta di nodi

Per inserire un oggetto l'albero è visitato ricorsivamente dal nodo radice. Un elemento è inserito in un MBR che necessita il minor numero di estensione delle dimensioni che l'aggiunta comporterebbe. A parità di numero di estensioni, viene scelto il nodo con MBR di area minima. Trovato il nodo foglia corretto, viene aggiunto l'oggetto vero e proprio. Se viene aggiunto un nodo ad un MBR che contiene già un numero-limite di elementi (di solito chiamato "C", capacity), la regione (MBR) viene divisa in due regioni con un algoritmo di split. Tale algoritmo realizza le due nuove regioni tendendo a creare MBR con area minima (tra tutti quelli possibili).

Bibliografia

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57. ISBN 0-89791-128-8
Lars Arge, Mark de Berg, Herman J.Haverkort, Ke Yi: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree, Proc. 2004 ACM SIGMOD international conference on Management of data, pp. 347–358. ISBN 1-58113-859-8
Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees: Theory and Applications, Springer, 2005. ISBN 1-85233-977-2
N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 (PDF), su dbs.mathematik.uni-marburg.de. URL consultato il 31 marzo 2008 (archiviato dall'url originale il 17 aprile 2018).

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su R-tree

Collegamenti esterni

R-Trees: A Dynamic Index Structure for Spatial Searching (PDF), su www-db.deis.unibo.it. URL consultato il 31 marzo 2008 (archiviato dall'url originale il 21 febbraio 2007).
An R-tree implementation in Common Lisp, su cliki.net.