[OSM-dev] spatial index - B-Tree over z-order curves vs R-Tree over GIST

Frederik Ramm frederik at remote.org
Thu Apr 9 00:36:54 BST 2009


pablo platt wrote:
> It uses B-Tree index so the only way I know to enable spatial index is to
> use space-filling-curves (z-order, morton codes)

I've not come across these terms but from your references it seems that 
this is very much the same as our "Quadtiles" approach. The OSM db is 
still based on MySQL which has no multi-dimensional indexes either so we 
   added a "quadtree tile" to each node which allows indexing. Since 
this happens on the application layer of course it makes our select 
queries quite ugly ("where (tile > x0 and tile <x1) or (tile > x2 and 
tile < x3) or (...) ...") but they're not there to win a beauty contest 
and the parser hasn't complained. Yet.

> My question is why PostGIS choose to use R-Tree over GIST.

I guess they had some reasons for it but I have no clue. One tends to 
assume that those who develop these things know what they do... until 
one day one looks at their source and finds comments that betray the 
fact that they're not any wiser than oneself ;)

> Using z-order
> with B-Tree seem simpler and supported out of the box
> by most databases. 

I don't think that the PostGIS developers cared about what was supported 
by other databases.


Frederik Ramm  ##  eMail frederik at remote.org  ##  N49°00'09" E008°23'33"

More information about the dev mailing list