What stuff do you need apart from the terrain data? If you just need to store the specific type of soil for each tile, you should be able to keep that to less than 8bits per tile. With 8bits you would need about 6.6Mb for the terrain, which shouldn't be a problem. Just store it as an array. If you have only 16 different types of landscape tiles, you can keep it to a 4bit array and then you only need 3.3Mb.
For the terrain data itself nothing beats an array.
If you have extra stuff, which I assume you do, you should decouple that from the terrain, as it is likely to be much more sparsely distributed. A quad tree is no bad solution, or you could use regular clusters that span X*X number of terrain tiles and contain a clean list of what goes where. Again that is easy to index and easy to predict preloading/swapping of if nescessary.
I don't understand why you want to use a tree for the regular terrain, but maybe I have misunderstood something.
For the terrain data itself nothing beats an array.
If you have extra stuff, which I assume you do, you should decouple that from the terrain, as it is likely to be much more sparsely distributed. A quad tree is no bad solution, or you could use regular clusters that span X*X number of terrain tiles and contain a clean list of what goes where. Again that is easy to index and easy to predict preloading/swapping of if nescessary.
I don't understand why you want to use a tree for the regular terrain, but maybe I have misunderstood something.