[OSM-dev] Proposal: Database accelerator and dirty tile marker based on simple algorithm.
nick at nickhill.co.uk
Sat Sep 16 21:46:45 BST 2006
Nick Hill wrote:
> So I propose that if we should use a quad-tree principle, it would be on
> the basis of coding complexity comparison, computing requirement, data
> locality in database (areas on the hard drive roughly corresponding to
> localities in real world) and whether the easier selection of larger
> areas is justifiable.
Developing this still further, we will want to have a scalable map which
operates over a wide range of zooms. At close zoom levels, fie features
are selected and shown. At lower zoom levels, large lakes and parks, A,
B, Motorways and rail lines shown. At lower level, A, Motorway and
intercity rail network shown. Lower level, Motorways and intercity
lines. Lowest zooms, very large features such as huge inland lakes. All
zooms, country outlines.
By using a quad-tree style tile to represent the 16
most-significant-bits of objects lat and lon (32 bits), the selection of
areas on a regional and country scale would be made simpler and less DB
To achieve this sort of scalability, we would need a table with
basically 3 fields. Quadtree-style tile 32 bit (with interleaved
lat/lon), Object zoom value (the maximum zoom level an object will
remain visible at) and reference to object.
There is a problem where large scale views of an area will constantly be
invalidated by small changes in the area, despite those changes not
affecting objects visible at the current zoom level.
For example, you may view the whole London area A-road network. From one
view to the next, the whole lot will be invalidated from tiny changes to
minor roads, which are not visible at your zoom level.
This is where the variable bitmask and zoom level become one of the same
If a feature with a zoom value of 0 is modified, only the smallest
invalidation tile has it's timestamp updated and the tile location
written to the invalidation table.
If a feature with zoom value 1 is modified or created, exactly the same
happens for 0. After that update, the last 2 bits of the quad-tree tile
are set to 0 and an entry is put into/timestamp updated for zoom level 1.
If a feature with zoom value 2 is modified or created, exactly the same
happens for 0 and for 1. After those updates, the last 4 bits of the
quad-tree tile are set to 0 and an entry is put into/timestamp updated
for zoom level 2.
and so on.
This way, a tile is only invalidated if an object which will show at
that zoom level is changed.
The table has a primary key based on invalidation tile and zoom level.
Inserts to the table are set to update on duplicate so only the freshest
time stamp for an area is kept.
I wonder if tomorrow I will understand what I have just written?
More information about the dev