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

[pablo platt]

On Thu, Apr 9, 2009 at 9:30 AM, <marcus.wolschon at googlemail.com> wrote:

> 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.


I understand that you map 2D data on a 1D array and then you index it with a
B-Tree.
This article explains how it works http://www.ddj.com/184410998.
It also says that R-Tree is always preferred but doesn't explains why.

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20090409/a609b859/attachment.html>