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

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.