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

[marcus.wolschon at googlemail.com]

On Thu, 9 Apr 2009 02:12:08 +0300, pablo platt <pablo.platt at gmail.com>
wrote:
> 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
data
> 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
never-to-be-changed
2D-tree.
However I could not find any multi-dimensional trees that can do a
rebalancing
in O(1) like an AVL-tree can.

So while this may be a good index for data-sets that never change it
quickly
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
performance.

Marcus