Árbol R+

Un árbol R+ es un método para buscar datos utilizando una ubicación, generalmente coordenadas (x, y) , y a menudo ubicaciones en la superficie terrestre . Buscar con un solo número es un problema resuelto; buscar con dos o más, y solicitar ubicaciones cercanas tanto en la dirección x como en la dirección y, requiere algoritmos más sofisticados.

Fundamentalmente, un árbol R+ es una estructura de datos de árbol , una variante del árbol R , utilizada para indexar información espacial .

Los árboles R+ son un compromiso entre los árboles R y los árboles kd : evitan la superposición de nodos internos insertando un objeto en múltiples hojas si es necesario. La cobertura es el área total que cubre todos los rectángulos relacionados. La superposición es el área total que está contenida en dos o más nodos. ^{[ 1 ]} La cobertura mínima reduce la cantidad de "espacio muerto" (área vacía) que cubren los nodos del árbol R. La superposición mínima reduce el conjunto de rutas de búsqueda a las hojas (aún más crítico para el tiempo de acceso que la cobertura mínima). La búsqueda eficiente requiere cobertura y superposición mínimas.

Los árboles R+ se diferencian de los árboles R en que: no se garantiza que los nodos estén al menos medio llenos, las entradas de cualquier nodo interno no se superponen y un ID de objeto puede almacenarse en más de un nodo hoja.

Debido a que los nodos no se superponen entre sí, el rendimiento de las consultas puntuales mejora, ya que todas las regiones espaciales están cubiertas por un solo nodo como máximo. Se sigue una única ruta y se visitan menos nodos que con el árbol R.

Dado que los rectángulos se duplican, un árbol R+ puede ser más grande que un árbol R construido con el mismo conjunto de datos. La construcción y el mantenimiento de los árboles R+ son más complejos que la construcción y el mantenimiento de los árboles R y otras variantes del árbol R.

• T. Sellis, N. Roussopoulos y C. Faloutsos . El árbol R+: un índice dinámico para objetos multidimensionales . En VLDB, 1987.