R*-árbol

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 12 de diciembre de 2019; la verificación requiere 1 edición .

árbol R*

Tipo de

estructura de datos

año de invención

1990

Autor

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider y Bernhard Seeger

Complejidad en los símbolos O

	Promedio	Lo peor
Consumo de memoria	O( n )	O( n )
Búsqueda	O ( iniciar sesión )
Insertar	O ( iniciar sesión )

Archivos multimedia en Wikimedia Commons

Los árboles R* son una variante de los árboles R que se utilizan para indexar información espacial. Los árboles R* tienen un costo de creación ligeramente mayor que los árboles R estándar, ya que es posible que sea necesario reorganizar los datos (eliminar + insertar), pero el árbol resultante generalmente tiene un mejor rendimiento de consulta. Como un R-tree estándar, puede almacenar puntos y datos espaciales. El árbol fue propuesto por Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider y Bernhard Seeger en 1990 [1] .

La diferencia entre árboles R* y árboles R

Minimizar tanto la cobertura como la superposición es importante para el rendimiento de los árboles R. Superposición significa que, al consultar o insertar datos, es necesario expandir más de una rama del árbol (debido al método de dividir los datos en áreas que pueden superponerse). La cobertura minimizada mejora la eliminación al permitir que las páginas completas se excluyan de las búsquedas con más frecuencia, especialmente para consultas con rangos negativos. El árbol R* intenta reducir ambos valores mediante una combinación del algoritmo de división de nodos escaneados y el concepto de reinstalación forzada en caso de desbordamiento de nodos. El enfoque se basa en la observación de que las estructuras de árbol R son muy sensibles al orden en que se insertaron los elementos del árbol, por lo que es más probable que las estructuras basadas en inserción (en lugar de carga masiva) no sean óptimas. Eliminar y volver a insertar elementos del árbol les permite "encontrar" un lugar en el árbol que sea más adecuado que su ubicación original.

Cuando un nodo se desborda, algunos de sus elementos se eliminan del nodo y se vuelven a instalar en el árbol. (Para evitar un restablecimiento en cascada sin fin causado por otro nodo que se desborda en esta operación, el procedimiento de restablecimiento solo se puede llamar una vez en cada nivel del árbol cuando se inserta cualquier elemento nuevo). Esto da como resultado grupos de elementos mejor agrupados en el nodos, reduciendo la cobertura de nodos. Además, a menudo se retrasa la división del nudo, lo que conduce a un aumento del llenado medio del nudo. La reinserción se puede considerar como una técnica para optimizar un árbol en crecimiento cuando un nodo se desborda.

Rendimiento

La heurística de partición mejorada produce páginas que son más rectangulares y, por lo tanto, más adecuadas para muchos algoritmos.
El método de reinserción optimiza el árbol existente, pero aumenta la complejidad.
Mantiene eficientemente puntos y datos espaciales.

Resultados de diferentes enfoques de partición en una base de datos de oficinas postales alemanas
R-tree con tabique Gutman cuadrado [2] .
Hay muchas páginas que se extienden de izquierda a derecha por toda Alemania y las páginas se superponen mucho. Esta no es una propiedad muy favorable para la mayoría de las aplicaciones, que a menudo solo necesitan pequeñas áreas rectangulares que se cruzan con muchas rayas.
R-tree con partición lineal Anga-Tan [3] .
Aunque los rectángulos no son tan largos como en el mosaico de Gutmann, el problema de las bandas afecta a casi todas las hojas de la página. Las páginas de hoja se superponen poco, pero las páginas man se superponen mucho.
Partición topológica R* de un árbol [1] .
Las páginas se superponen muy poco porque el árbol R* intenta minimizar las páginas superpuestas y la reinserción optimiza aún más el árbol. La estrategia de partición tampoco favorece las bandas, por lo que las páginas resultantes son más adecuadas para aplicaciones de mapeo.

Algoritmo y complejidad

El árbol R* utiliza el mismo algoritmo para consultas y eliminaciones que el árbol R normal .
Para la inserción, el árbol R* utiliza una estrategia combinada. Para los nodos de hoja, se minimiza la superposición, mientras que para los nodos internos, se minimizan las dimensiones lineales y el área.
Para la partición, el árbol R* utiliza una partición topológica, que selecciona una partición de los ejes a lo largo del perímetro, luego se minimiza la superposición.
Además de una estrategia de división mejorada, el árbol R* intenta evitar la división cuando se reinsertan objetos y subárboles en el árbol, en el espíritu del concepto de un árbol B equilibrado .

Las consultas en el peor de los casos y la complejidad de eliminación son idénticas a las de un árbol R. La estrategia de inserción de árbol R* tiene complejidad y es más compleja que la estrategia de división lineal ( ) del árbol R, pero es menos compleja que la estrategia de división cuadrada ( ) para el tamaño de página de los objetos, y tiene una pequeña contribución a la complejidad general. La complejidad general de la inserción sigue siendo comparable a la de un árbol R: una reinserción afecta como máximo a una rama del árbol y, por lo tanto, genera inserciones repetidas, cuyo rendimiento es comparable al de un árbol R normal. Entonces, la complejidad general de un árbol R* es la misma que la de un árbol R normal. ${\mathcal {O}}(M\log M)$ ${\mathcal {O}}(M)$ ${\mathcal {O}}(M^{2})$ $METRO$ ${\mathcal {O}}(\log n)$

La implementación del algoritmo completo debe manejar muchos casos de esquina y situaciones dependientes, que no se tratan aquí.

Notas

↑ 1 2 Beckmann, Kriegel, Schneider, Seeger, 1990 , p. 322.
↑ Guttman, 1984 , pág. 47.
↑ Ang, Tan, 1997 , pág. 337–349.

Literatura

Beckmann N., Kriegel HP, Schneider R., Seeger B. El árbol R*: un método de acceso eficiente y robusto para puntos y rectángulos // Actas de la conferencia internacional ACM SIGMOD de 1990 sobre gestión de datos - SIGMOD '90 . - 1990. - ISBN 0897913655 . doi : 10.1145 / 93597.98741 .
Guttman A. R-Trees: una estructura de índice dinámico para la búsqueda espacial // Actas de la conferencia internacional ACM SIGMOD de 1984 sobre gestión de datos - SIGMOD '84 . - 1984. - ISBN 0897911288 . -doi : 10.1145/ 602259.602266 .
Ang CH, Tan TC Nuevo algoritmo de división de nodos lineales para árboles R // Actas del 5º Simposio Internacional sobre Avances en Bases de Datos Espaciales (SSD '97), Berlín, Alemania, 15 al 18 de julio de 1997 / Michel Scholl, Agnès Voisard. - Springer, 1997. - T. 1262. - (Lecture Notes in Computer Science). -doi : 10.1007 / 3-540-63238-7_38 .

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión

Estructuras de datos
Liza	formación lista enlazada simple lista doblemente enlazada lista de pases
Árboles	árbol B Árbol de búsqueda binario árbol AVL árbol rojo-negro montón
cuenta	Gráfico dirigido Gráfico Acíclico Dirigido Diagrama de decisión binaria Hipergrafo
Otro	Tabla de picadillo Pila