R*tree

Introducción
R*-tree
El R*-tree, al igual que el R-tree convencional, es una estructura de datos basada en MBRs, arbórea, multidimensional, balanceada en altura y almacenada en disco. Esta estructura de datos fue propuesta en [BKS+90] para solucionar el principal inconveniente que presentaban los R-trees en el procesamiento de consultas espaciales. El problema consistía en la posibilidad de queexista un elevado índice de solape entre los MBRs que hay en los nodos de un mismo nivel en el R-tree, provocando una reducción del rendimiento ante tales operaciones.
Objetivos
-Entender el funcionamiento de un R*-tree, aprender el funcionamiento de las funciones de inserción, eliminación y búsqueda.
Características
El diseño del R*-tree como método de acceso espacial introduce una nuevapolítica para la inserción denominada, reinserción forzada. En ella, si un nodo se desborda por primera vez en un determinado nivel, no se realiza la división del mismo de forma inmediata, sino que primero se extraen w entradas de dicho nodo y después se reinsertan en el R*-tree.
La reinserción forzada se utiliza para reducir numero de divisiones de nodos desbordados y reorganizar dinámicamente elR*-tree tiene en cuenta los siguientes objetivos:
1. Se debe minimizar el solape (overlap) entre regiones minimales cubiertas por nodos que están en el mismo nivel del árbol. Cuanto menor sea el solape entre MBRs, menor es la probabilidad de tener múltiples caminos de búsqueda.
2. Se debe minimizar también los perímetros de los MBRs. El MBR preferido es el que tiene forma cuadrada, ya quees la representación rectangular más compacta.
3. Se debe maximizar la utilización del almacenamiento.
La complejidad de los algoritmos de división de nodos es de O(k*N*logN) para un nodo con N MBRs [BKS+90].
La eficiencia de las consultas sobre R*-trees depende de lo buena que sea la distribución de MBRs en los nodos. Por ello, el algoritmo de inserción de objetos en un R*-tree es la fase másimportante de cara a tener un buen rendimiento para las consultas (árbol más compacto y reducido).


Se describirán los algoritmos de inserción, borrado y búsqueda de MBRs en un R*-tree, que se ilustrarán en base a la estructura de datos representada en la Figura 2.7. En la parte izquierda (Figura 2.7.a) se muestran varios MBRs bidimensionales y la correspondiente estructura de archivo parael R*-tree de orden (2, 3) a la derecha (Figura 2.7.b), donde los nodos del árbol se corresponden con páginas del archivo.
Inserción R*
Sea N un nodo interno de un R*-tree, cuando insertamos un MBR S, en un nodo hijo de N, se necesita escoger algún MBR, por ejemplo R, en N como el MBR padre de S. Puede que R necesite agrandarse para contener a S. Una técnica de optimización es escoger a R en Ntal que necesite la menor expansión de solape para contener a S. Evidentemente, cuando R se agranda, el factor de solape de R en N es probable que se incremente. También es evidente que si R contiene ya a S, entonces no se necesita ninguna expansión para R. Minimizando el solape se tiende a minimizar el número de subárboles que hay que seguir para realizar las operaciones de búsqueda.Definición.Solape de un MBR R con un nodo N de un R*-tree. Sea N un nodo interno de un R*-tree. El solape de un MBR R en N es la suma de las áreas solapadas de los otros MBRs de N con R.
En la Figura 2.8, mostramos en primer lugar (Figura 2.8.a) varios de los MBRs incluidos en un nodo N, y en segundo (Figura 2.8.b) lugar el solape de R en N.


Para presentar la descripción del algoritmo de inserciónen un R*-tree consideramos los siguientes parámetros: sea T el puntero a la raíz del R*-tree y (S, PS) el par a insertar, donde PS es la dirección del puntero al elemento (nodo u objeto) que cubre al MBR S. Además debemos considerar a L, que inicialmente es el nodo raíz, como el nivel donde va a ser insertado el par (S, PS). Cada nivel tiene un indicador de desbordamiento, mostrando si ha...