In the open outdoor environment the system uses timing measurements to locate transmitters - so the database is not of signal fingerprints in that instance but of transmitter ID and locations. In the UK there are a few hundred MW, DAB and DVB transmitters, and a few tens of thousands of cellular basestations. The database of a given country's transmitters is therefore only likely to require a few hundred kilobytes or few megabytes of storage. In the indoor environment the system uses signal fingerprinting, magnetic anomalies, and SLAM to constrain the drift on the position estimate of a user as they moves around a building. The resulting signal strength maps could be stored for future use if desired but this is not necessary for the system to function again next time, the memory is only required during that particular journey to allow position drifts to be observed and corrected (see my ION paper or read about DP-SLAM). In this day and age of 16GB+ SD cards I really don't lose any sleep about database storage requirements.
To help you understand the the outdoor positioning database aspects, consider driving along a motorway into a city. Nice open sky environment along the way in, GPS available, the system learns about the locations of the DAB transmitters, DVB transmitters, cellular, etc. As you move into the city and lose satellites, you can still detect the terrestrial transmitters you calibrated on the way in and continue to calibrate the locations of new ones too as they come into range and others drop out of range. Remember operating in a given city you will pick up the same handful of DAB and DVB transmitters across the whole region, but encounter hundreds of cellular transmitters. The point is that with a combination of the calibrated DAB and DVB transmitters from your drive in, the cellular transmitters you have already located, and sporadic GPS you can end up determining the locations of all the cellular transmitters in that city over a short period of time exploring the region. Then something happens to GPS one day - a jamming event, coronal mass ejection, etc. that removes GPS not for a few minutes at a time as usual, but for an extended period of time - NAVSOP has built up a rich set of backup sources to allow uninterrupted operations, even under long periods of GPS outage.