[OSM-dev] Binary OSM db (was: Re: on-disk indexing of geodata)

[Marcus Wolschon]

2008/10/17, Sascha Silbe <sascha-ml-gis-osm-dev at silbe.org>:


Hello Sasche and Freek,

I'm just back from the weekend and trying to catch up on
your discussion. I have a few questions:

=== 1D-Indexing ====

So, for an 1D-index you have ended up with a tree of order 8.
Like the a file with the following record-formats:
middle-node:
* recordNumber[32bit] of (current value>>3)
* recordNumber[32bit] of (current value>>3+1)
...
* recordNumber[32bit] of (current value>>3+7)

* record-numbers start at 2
* a record-number of 0 denotes an empty entry
* a first record-number of 1 denotes a leaf of the tree
* a middle-node consisting of only 0 is an unused block

leaf:
* leaf-marker [2x32bit]
* ID-Number        of indexed OSM-Object 1 [32bit]
* record-number of indexed OSM-Object 1 [32bit]
* ID-Number        of indexed OSM-Object 2 [32bit]
* record-number of indexed OSM-Object 2 [32bit]
..
* ID-Number        of indexed OSM-Object 6 [32bit]
* record-number of indexed OSM-Object 6 [32bit]

did I understand this correctly?

=== 2D-Indexing ====

For a 2D-index you propose a space-filling curve that
maps a bouding-box into a list of 1D-intervalls and
then use the same 1D-indexing?

=== Queestion ====

> On Fri, Oct 17, 2008 at 07:47:14PM +0200, Freek wrote:
>
>> Looks like we have enough ideas for adding indexes and such to an OSM
>> binary format, so if the rest of the structure is fixed I think we can
>> get it off the ground (I wouldn't mind at least helping out here and
>> there).
> OK, so what do "we" want in a binary DB? Currently there is (in my
> implementation):
>
> Node/way/relation internal <-> external id:
>     - int -> ext O(1)
>     - ext -> int O(log n)

What do you mean by externalId and internalID?

You also mentioned a notion like "O(4n)". The Big-O -notation
does not allow for constant factors. What do you mean with to
express with this?

Marcus