I've done a proof-of-concept with GDBM (a simple hash-key-value system), and I was able to reduce disk space requirements (on a 1k-block file system) by about 40%. (That number may not be representative; it is based on only about 10,000 zoom-level-0 maps.)

I'm still investigating alternatives, though. Someone mentioned CDB, but that's less useful in a constantly-changing map cache scenario. Maemo Mapper already uses sqlite3, so if I can reuse it for the map cache (POI would still be in a separate database) with sufficient performance, I will prefer to do that. sqlite3 (or any relational database, for that matter) could also give me the opportunity to implement more complex features, such as "aging out" (based on either time or fixed-disk-space) of older, not-recently-accessed maps .

I'm also open to suggestions.