Can R-árboles mantienen orden z utilizando las 2 dimensiones?

Question

Estoy escribiendo una implementación de un árbol R basado en el artículo original de Guttman. Estaba pensando acerca del uso de un R-Tree para un programa que estoy escribiendo que implica una gran cantidad de rectángulos en la pantalla que se puede mover / cambiar de tamaño con el ratón.

Quiero eficiente solamente seleccionar rectángulos que se encuentran en un rectángulo particular y atraerlos (en lugar de iteración a través de más de 100 artículos potencialmente y comprobando si se cruzan los límites). El problema que estoy encontrando después de un par lee de papel de Guttman es que el orden-z no se puede mantener por objetos 2D.

Por ejemplo, si muevo un objeto, que sería eliminado y luego volver a insertar. Cuando es reinsertado, el nodo se inserta a no sería capaz de hacer un seguimiento de la orden adecuado. La mayor parte de la implementación de un R-árbol que he visto el uso de una matriz y acabo de encontrar la posición vacía. El re-inserción destruiría esencialmente cualquier posicionamiento orden z.

Así que cuando voy a sacar todos los rectángulos que se cruzan con un rectángulo, el orden en que se devuelven no es necesariamente correcto.

¿Estoy equivocado en este supuesto? Estaba pensando en lugar de utilizar una matriz, que podría utilizar un árbol AVL o Rojo-Negro y utilizar un Comparer que compara el índice z para insertar en el árbol. De esta manera, orden z se mantiene siempre (y es el factor más importante).

Yo estaba también pensando en la clasificación ellas cuando se vuelven, pero esto podría ser más caro que estoy pensando.

Answer 1

R-árbol no se supone que los registros de orden de las respuestas de alguna manera.

Sólo una especie responder. No es demasiado lento.

Por cierto, puedo enviar mi código R-árbol. Funciona bien para mí, pero sería muy útil si alguien sería comprobar es que lo Guttman o Beckman escribieron en papeles suyos ...

Orden de indexación espacial es esencialmente diferente de orden estricto ... es diferencia entre la indexación espacial y solo árbol B +.

También puede tener dos índices y unirse a ellos. ¿Está usted realmente necesita shure índice? Algo funciona lento?