Deleting items breaks the index

[flusflas]

I'm new with rtree (and R-trees in general) and I don't know how an R-tree is implemented (I just know the high-level theory), but I've found a weird behavior when trying to delete items from an index.

For an index with a few items, deleting some of them generally doesn't break anything. However, when complexity grows and I delete one item, points that before matched with other items stop doing it.

As I don't understand this behavior, I created a repo with a sample code to illustrate my problem. This code just:

1. Reads a list of countries geometries from a geojson file.
2. Adds every polygon bounds to an index (using a UUID for each polygon).
3. Generates one point for each polygon.
4. Checks every generated point has at least one match using the index.
5. Deletes the polygons of only one country.
6. Checks every generated point again.
7. Prints the data of every point without matches with its country.

In the example, I'm deleting all USA polygons, but all the points inside USA keeps matching. However, other points from other countries fail, even though I didn't remove its country from the index.

Maybe I'm missing something about R-trees, but I think this doesn't make sense. Chances are I'm using it wrong, but I don't know why. I'm sorry this issue involves some work to check, but would appreciate some help.

[gbrunner]

@flusflas A coworker and I noticed this issue with deletion recently too. We are thinking it's an issue in libspatialindex. Any insight @mikedh ?