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

[Matt Amos]

On Thu, Apr 9, 2009 at 11:07 AM, pablo platt <pablo.platt at gmail.com> wrote:
>> I've not come across these terms but from your references it seems that
>> this is very much the same as our "Quadtiles" approach.
>
> According to this http://www.ddj.com/184410998 z-order curve is a case of
> "Quadtiles".

yes. what we call quadtiles is just a morton numbering.

>> The OSM db is still based on MySQL which has no multi-dimensional indexes
>> either so we  added a "quadtree tile" to each node which allows indexing.
>> Since this happens on the application layer of course it makes our select
>> queries quite ugly ("where (tile > x0 and tile <x1) or (tile > x2 and tile <
>> x3) or (...) ...") but they're not there to win a beauty contest and the
>> parser hasn't complained. Yet.
>
> Is the tiles resolution predetermined or is the tree dynamic and when a tile
> get overpopulated you divide it to 4 child tiles?
> I don't understand how you make a query in a dynamic tree.

our morton numbers are calculated at a fixed depth. no splitting is done.

cheers,

matt