The R-Tree We Built and Turned Off

Nockawa’s Blog · 1 day ago · discuss

Typhon's spatial index can promote a dense cell from a linear scan to a per-cell R-Tree. It ships with that promotion disabled — the threshold is int.MaxValue, so no cell ever promotes. The tree is faster at the thing it was built to be faster at, and turning it on made the whole tick up to 1.75 times slower. Here is why, what the memory hierarchy has to do with it, and what it says about reading a data structure's cost.