This is a real R-tree (Guttman, 1984), built with the same insertion algorithm PostGIS's GiST-based spatial index runs under the hood — not a stand-in grid. Every object is inserted one at a time:
- ChooseLeaf walks down from the root, at each internal node picking the child whose bounding box needs the least area enlargement to contain the new object.
- When a node overflows past its capacity
M, a quadratic split picks the two entries that would waste the most area if grouped together as seeds, then distributes the rest by whichever group needs less enlargement.
- A query rectangle is answered by real R-tree search: at each internal node, only children whose bounding box overlaps the query are entered — the rest are pruned without looking inside them at all, however many objects they hide.
Drag a box on the map to query. Amber-outlined nodes were opened and their objects checked one by one; red-dashed boxes are subtrees the index skipped entirely — that's the performance win a spatial index gives PostgreSQL over scanning every row.