Si has estado siguiendo el Serie de índices espacialesComenzó con la necesidad de índices multidimensionales y una introducción a curvas que llenan el espacioseguido de una inmersión profunda en sistemas de red (GeoHash y Google S2) y mosaico (Uber H3).
En esta publicación, exploraremos el Árbol R estructura de datos (estructura basada en datos), que se utiliza popularmente para almacenar datos multidimensionales, como puntos de datos, segmentos y rectángulos.
Por ejemplo, considere el plano de una universidad que se muestra a continuación. Podemos utilizar la estructura de datos R-Tree para indexar los edificios en el mapa.
Para ello, podemos colocar rectángulos alrededor de un edificio o grupo de edificios y luego indexarlos. Supongamos que hay una sección mucho más grande del mapa que representa un departamento más grande y necesitamos consultar todos los edificios dentro de un departamento. Podemos usar el árbol R para encontrar todos los edificios dentro (parcial o totalmente contenidos) de la sección más grande (rectángulo de consulta).
En la figura anterior, el rectángulo rojo representa el rectángulo de consulta, utilizado para preguntar…