Can R trees support z-order when using two dimensions?

Question

I am writing an R-Tree implementation based on the original Guttman paper. I was thinking about using R-Tree for the program I am writing, which includes many rectangles on the screen that you can move / resize with the mouse.

I want to efficiently select only the rectangles that are in a particular rectangle and draw them (instead of repeating through potentially more than 100 elements and checking for border intersections). The problem I discovered after a couple reads Guttman's article is that z-order is not supported for 2D objects.

For example, if I move an object, it will be deleted and then inserted again. When it is inserted, the node that it inserted will not be able to track the correct order. Most of the R-Tree implementations I've seen use an array and just find an empty position. Reinserting will substantially destroy any z-order positioning.

So, when I go to draw all the rectangles that intersect with the rectangle, the order they return is not always correct.

Am I really mistaken in this assumption? I was thinking instead of using an array, I could use the AVL or Red-Black tree and use Comparerthat compares with z-index to insert into the tree. Thus, z-order is always maintained (and this is the most important factor).

I also thought about sorting them out when they are returned, but it can be more expensive than what I think.

Answer 1

The R-tree should not somehow order response records.

Just select an answer. It is not too slow.

By the way, I can send you my r-tree code. This works fine for me, but it would be very helpful if someone checked it out what Gutman or Beckman wrote in his works ...

The spatial indexing order is significantly different from the strict ordering ... this is the difference between spatial indexing and just B + -tree.

. , ? - ?