Ideal database for geo (map) data

I’m looking for suggestions for an ideal database or data structure for storing a map. Essentially, the map consists of “ways” which are like roads, paths, etc. Ways contain nodes (which have a latitude and longitude coordinate, and sometimes an altitude.)

Any such database or structure:

1. should be able to locate all the nodes in a bounding box quickly (milliseconds)

2. optionally, should not considerably slow down when a large number of nodes are in a bounding box vs. a small number of nodes, or if the bounding box is large

3. should be able to find nodes that connect directly: e.g. the node which connects two ways

4. could be read only

5. should be compact (avoids wasting space) – I’m looking to fit a map of the UK into less than 1 GB. I have a sat nav that does this with about 800 MB of space on an SD card.

I was thinking initially of quad trees to store ways. But a fast implementation is tricky, and they don’t work for individual nodes; all nodes get put in the smallest bbox possible.

(I’m deliberately using the same terminology of Open Street Map because I plan to use that data.)

Answer

I’d recommend with PostGIS 1.5 using the geography type as it’s suited to what you want, however my only concern with using something like this on an embedded device would be memory usage.

I’ve built something vaguely related using a non GIS database (firebird) in Java and the performance was more than adequate for retrieving points within a bounding box (although fancy SQL was required which isn’t the case with PostGIS).