2008/10/17, Sascha Silbe <[EMAIL PROTECTED]>:
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 _______________________________________________ dev mailing list [email protected] http://lists.openstreetmap.org/listinfo/dev
