[OSM-dev] Quad- and R-Trees

[marcus.wolschon at googlemail.com]

On Tue, 20 Jan 2009 14:39:39 +0100, Dominik Spies <kontakt at dspies.de>
wrote:
> Hi,
> 
> this is not an OSM-only question, but it is related to OSM and I don't
> now where to look for people with same experience in this topic.
> So I hope you can provide some help.
> Quadtrees and R-Trees are used for indexing spatial data. I read -
> without an explanation - that quadtree have disadvantages with
> indexing geospatial data, because of different densities of data
> (rural and urban areas).
> 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.

Exactly.
That is the advantage of an R-Tree.
You want your tree to be as balanced
as possible.

Does anyone know of a way to do a 2D-AVL-tree?

Marcus