Introducción al árbol R

R-tree es una estructura de datos de árbol utilizada para almacenar índices de datos espaciales de manera eficiente. Los árboles R son muy útiles para consultas y almacenamiento de datos espaciales. Algunas de las aplicaciones de la vida real se mencionan a continuación: 
 

• Indexación de información multidimensional.
• Manejo de coordenadas geoespaciales.
• Implementación de mapas virtuales.
• Manejo de datos del juego.

Ejemplo : 
 

Representación del árbol R : 
 

Propiedades del árbol R : 
 

• Consiste en una sola raíz, Nodes internos y Nodes de hoja.
• Root contiene el puntero a la región más grande en el dominio espacial.
• Los Nodes principales contienen punteros a sus Nodes secundarios donde la región de los Nodes secundarios se superpone completamente a las regiones de los Nodes principales.
• Los Nodes hoja contienen datos sobre el MBR de los objetos actuales.
• MBR: la región límite mínima se refiere al parámetro de cuadro límite mínimo que rodea la región/objeto en consideración.

Comparación con Quad-trees : 
 

• Se requiere la optimización del nivel de mosaico en Quad-trees, mientras que en R-tree no requiere dicha optimización.
• El árbol cuádruple se puede implementar sobre el árbol B existente, mientras que el árbol R sigue una estructura diferente de un árbol B.
• La creación de índices espaciales en árboles cuádruples es más rápida en comparación con los árboles R.
• Los árboles R son más rápidos que los árboles cuádruples para las consultas de vecino más cercano, mientras que para las consultas de ventana, los árboles cuádruples son más rápidos que los árboles R.