Mapping Techniques for (3D) Games?

John Kelley asks: "I'm a developer for a new company that is developing a new moderately multiplayer real-time strategy Game and I've been charged with finding a data structure to effiently store map data. Does anyone have any experience with this? I have no clue what kind of data structure would be ideal for this but I'm sure someone does. We plan on having 1024x1024 sized maps and the game is slotted to hold 25 players in a 3D world akin to Age of Empires 2. Keep in mind that there are approximately roughly 256 different buldings, 32 different terrain types, etc..."