[OSM-dev] HTTP OSM Server - index

[marcus.wolschon at googlemail.com]

On Thu, 05 Mar 2009 18:26:12 +0100, Dick Marinus <dick at mrns.nl> wrote:
> Op donderdag 05-03-2009 om 08:25 uur [tijdzone +0100], schreef
> marcus.wolschon at googlemail.com:
>> So...is your index a list, tree, heap or hashtable, ... of
>> nodetile/waytile/... -structures?
>> How is your index stored on disk?
>> How are the required nodetile-structs loaded
>> into memory?
> 
> Well at this moment it's an ordinary sorted list :)
> But it might be a good idea to use an advanced index for the tile to
> ways index. The index is stored as sequential serialized structs.
> 
> To load a required nodetile from disk I'll seek through the sequential
> dump of nodetiles which have a fixed record size. The nodes are already
> sorted by id in planet.osm. By guessing an address and watching the
> value I'll know to look forward or backward.

So using a heap-search you basically get your search down to
O(log(n)). Fast enough.

init:
 maxRecord=filesize/recordsite
 minRecord=0
 currentRecord = maxRecord/2
 currentID = load(currentRecord)
 findID=$input

while findID != currentID
 if (findID < currentID)
   maxRecord = currentRecord 
 else
   minRecord = currentRecord 
 currentRecord = maxRecord/2

output:
 currentRecord

While your aproach is space-optimal it takes O(m+n)
to insert new elements into the list (m=size of index,
n=size of new elements, new elements are already sorted)

While increasing the disk-space from O(m) to
O(mlog(m)) you could get the merge-time down to
O(nlog(m+n)) with a tree-structure. Unless you want
not to merge the regular diffs but to regenerate
everything every time.

Marcus