[OSM-dev] on-disk indexing of geodata

[Sascha Silbe]

On Fri, Oct 17, 2008 at 06:10:51PM +0200, Freek wrote:

>> OK, so you just use pointers (=> index gets much larger)
> Ah, you're using the fact that your tree is a complete fan-out-8 tree 
> (except for the last part)?
Exactly.

>> and often give up locality (even if you spread some free blocks 
>> across the index).
> If your blocks are so large that seeking for them takes about as long 
> as retrieving them, it should not be that big a problem. I think a 
> fan-out of 8 is quite low.
Interesting point, might be worth some experimentation. To be honest, 
I've chosen that value rather arbitrarily - power of 2, overhead 
somewhere around 10%. :)

["constant" bulk database with invalidation + "dynamic" database with 
pointer-based indices for updates]
> That might be quite a good idea in OSM practice, you just rebuild the 
> bulk database every so often. Perhaps you can even just use an 
> internal-memory data structure (KD-tree, quad tree, something like 
> that) for the updated part.
Depending on the application, that may also be a useful approach. The 
current mmap() based implementation has the nice side effect that the 
database effectively resides in the OS cache => startup overhead is 
minimal, multiple processes share the data. For a long-running server 
process this might not matter, though.

CU Sascha

-- 
http://sascha.silbe.org/
http://www.infra-silbe.de/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 481 bytes
Desc: Digital signature
URL: <http://lists.openstreetmap.org/pipermail/dev/attachments/20081017/c6157ddc/attachment.pgp>