ALGORITMIAHENRRY

Indice:
2.6 R*-tree .............................................................................................................. 29
2.6.1 El R-tree como base para el R*-tree .......................................................... 29
2.6.2 Características principales del R*-tree ...................................................... 33
2.6.3 Algoritmos para el mantenimiento de un R*-tree....................................... 35
2.6.3.1 Algoritmo de inserción .................................................................... 35
2.6.3.2 Algoritmo de borrado ......................................................................... 40
2.6.3.3 Algoritmo de búsqueda .................................................................... 41
2.6.4 Algoritmos para el procesamiento deconsultas utilizando R*-trees como
método de acceso espacial ......................................................................... 42
2.6.4.1 Etapas en el procesamiento de consultas espaciales utilizando R*-
trees ..................................................................................................... 42
2.6.4.2 Algoritmos para el procesamiento de consultas espacialesutilizando
R*-trees ................................................................................................ 44
2.6.4.2.1 Algoritmos para la consulta exacta ............................................ 44
2.6.4.2.2 Algoritmos para la consulta en rango ....................................... 45
2.6.4.2.3 Algoritmos para la consulta del vecino más próximo ................ 46










2.6R*-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 que exista 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. Además, en [BKS+90] se confirma la observación hecha en [RoL85], de que un factor clave para el rendimiento de un R-tree respecto al procesamiento de consultas es la organización de los MBRs en dicho método de acceso durante el proceso de inserción.2.6.1 El R-tree como base para el R*-tree
El R-tree [Gut84] es una estructura de datos arbórea multidimensional basada en MBRs, balanceada en altura y almacenada en disco, derivada del B+-tree [Com79]. Este método de acceso es apropiado tanto para la indexación de puntos como de objetos en un sistema de bases de datos espacial. Los puntos, MBRs u objetos se almacenan en los nodos hoja del árbol oen un archivo k-dimensional de datos asociado al R-tree, mientras que en los nodos internos están los MBRs que cubren el área de los elementos del árbol que hay en un nivel inferior. Los nodos hoja contienen punteros a los objetos o punteros nulos si en ellos se almacenan puntos o MBRs, en lugar de punteros a sus nodos hijo como ocurre con los nodos internos. De forma general, podemos decir queesta estructura arbórea multidimensional organiza una colección de objetos representados por sus MBRs. A menudo, los nodos se corresponden con páginas de disco, y por tanto los parámetros para definir el árbol se escogen con el objetivo de optimizar el procesamiento de una consulta sobre él. Nótese que en un R-tree los MBRs que están en nodos internos pueden solaparse, es decir, MBRs en diferentesentradas de un nodo pueden tener un área de solape común. Éste es un inconveniente importante del R-tree convencional, puesto que si hay un elevado índice de solape entre los MBRs que forman el R-tree puede producir un bajo rendimiento en el procesamiento de consultas, ya que es necesario visitar varios nodos para determinar si un objeto determinado está en el árbol. En la Figura 2.5 se...