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

pablo platt pablo.platt at gmail.com
Thu Apr 9 11:34:18 BST 2009


On Thu, Apr 9, 2009 at 1:15 PM, Matt Amos <zerebubuth at gmail.com> wrote:

> On Thu, Apr 9, 2009 at 12:36 AM, Frederik Ramm <frederik at remote.org>
> wrote:
> > 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
>
> mysql has had a spatial index type (R-Tree) since version 4.1, but
> only for myisam tables which means no transactions or foreign keys :-(
>
> >> 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.
>
> as marcus has pointed out the performance of 1-d indexes for 2-d data
> is often poor. for further reading i recommend "Foundations of
> Multidimensional and Metric Data Structures" by H. Samet
> (http://www.cs.umd.edu/~hjs/ <http://www.cs.umd.edu/%7Ehjs/>) which is
> pretty comprehensive.


Thank you, I'll order a copy.

>
>
> cheers,
>
> matt
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20090409/7ac74e3e/attachment.html>


More information about the dev mailing list