[OSM-dev] Quad- and R-Trees

[Matt Amos]

On Tue, Jan 20, 2009 at 1:57 PM, jh <jh at foobar.de> wrote:
> Dominik Spies schrieb:
>> I could not find any helpfull information regarding this. Is this
>> correct? If yes why? The only reason I can imagine ist that the
>> quadtree will be very unbalanced.
>
> Yes, but I don't think that this should pose practical problems.
> This site and the related Books might be helpful:
> http://donar.umiacs.umd.edu/quadtree/

i recommend "foundations of multidimensional and metric data
structures" linked to above. it is massive, generally well-explained
and has the most thorough bibliography i've ever seen.

its a disadvantage that quadtrees can be unbalanced, but it can be
turned into an advantage. since no global rebalancing takes place, the
code for inserting and deleting can be simpler. it also permits higher
concurrency because fewer locks need to be held.

cheers,

matt