Anyway, back to GPS... Each road seems to be stored in pretty good detail. Plus the outline of bodies of water, etc. It continues to boggle my mind the amount of points contained, let alone the algorithms used to calculate routes.
Not that I know anything specific the the formats used to store map data, but think of it this way:
Even ignoring anything clever such as compression, stripping redundant data, etc (all of which I would be pretty sure is part of the commercial file formats!), the map detail and road layouts are stored in very efficient vector format. Assume there is on average one set of coordinates per 50 metres of typical road / river / feature (probably about the right order of magnitude for urban environments, conservative for rural areas, where you can often see the "jagginess" on the SatNav due to successive points being located further apart), and assume the coordinates are saved as a pair of double precision (4-byte) numbers, that gives about 8 bytes per 50 metres of road, or say 160 bytes per kilometre, or more than 6,000 km of road (or river, lake outline, etc) per megabyte.
Just doing some very basic maths, and realising that RAM on such devices is now measured in hundreds of MB or several GB, and you can see that there is plenty of room for some fairly highly detailed mapping!