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

marcus.wolschon at googlemail.com marcus.wolschon at googlemail.com
Thu Apr 9 07:30:48 BST 2009

On Thu, 9 Apr 2009 02:12:08 +0300, pablo platt <pablo.platt at gmail.com>
> Hi,
> I posted this question in the forum but I think that the list is more
> active.
> PostGIS uses R-Tree index over GIST.
> I'm trying to understand if it is possible to use couchDB for storing and
> indexing the osm data.
> couchdb is a schema less db for storing documents. Each document store
> encoded as JSON.
> 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)
> to translate a lat,lng to a number and then index all the numbers using a
> B-Tree.

>From what I found out you usually do not use a Z-curve or Hilbert-Curve
on a 1-dimensional index but you use it while constructing a
However I could not find any multi-dimensional trees that can do a
in O(1) like an AVL-tree can.

So while this may be a good index for data-sets that never change it
becomes highly unbalanced in datasets that are changed frequently.

I guess an R-Tree (also called 2D (R)ange-tree) was just easiest with the
existing indexing datastructures they had and it provides adequate


More information about the dev mailing list