[dylrich]

I'm interested in their reasons for not using an R-Tree or an R*-Tree for the index. I know they mentioned the debate in this post but I'm quite curious how they arrived at their decision. Have they done performance tests with both methods? Many other high performance applications use R-Tree based structures, and I've always been under the impression that R-Trees usually outperform Quadtree style indexes in PIP queries.

[repsilat]

Funny, almost every r-tree in the codebase at a former job of mine eventually became a performance problem and got replaced by square fixed-size buckets.

Of course, it helped that most of the queries we did could be phrased like "Find all things within a fixed (and known ahead of time) radius of this point." R-trees are much more versatile, but much slower to query and much much slower to construct/maintain.