State of rtree different after insert/delete (0,0,0,0) and insert/delete (0,0,10,10)

Author: Robert-M-MuenchCreated Jan 5, 2021Updated Jun 12, 2022

The state of rtree is different after insert/delete (0,0,0,0) and insert/delete (0,0,10,10).

The difference is that maxHilbert changed from 0 to 34 in the (0,0,10,10) case. Is this intentional or a bug? I expect that the rtree behaves the same, independently of what kind of rectangles I have.

Maybe it's not relevant but I have one case, where an other rTree gives a correct search result whereas this one here is wrong. I search for P1 = (1,1,1,1) and P2 = (1001,1,1001,1) The sequence is:

Node-1: (0,0, 2000, 1000) Node-12: (0,0,2000,1000)

P1 and P2 are correctly found.

Adding Node-13 and changing Node-12 by remove and insert:

Node-1: (0,0, 2000, 1000) Node-12: (0,0,1000,1000) Node-13: (1000,0,2000,1000)

P1 correctly found, P2 reports Node-1 and Node-12 as result, which is wrong.

Source: Workiva/go-datastructures