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

[Matt Amos]

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/) which is pretty comprehensive.

cheers,

matt