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:
should be able to locate all the nodes in a bounding box quickly (milliseconds)
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
should be able to find nodes that connect directly: e.g. the node which connects two ways
could be read only
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.)