I know this is an old post and i am not 100% sure this will help at all but i am going to state my current TileMap Solution and you can take from it what you will.
First off i use a quad tree for storing my tile's information i do not store graphical information in my quad tree instead of i store Sectors which are composed of multiple tiles the sector has an X and a Y coordinate which is an absolute coordinate of it in the world. The sectors contain an array of unsigned intergers these are actually TileIDs
. The sectors will also contain other objects that may not be tile related ( this is so i only make one quad tree query per update and get all game objects ) <- this is just a side note since you seem to be consenderd about optimization.
anyways i just draw it like a normal tile map after retreaving the tile IDS i index an array which has my actual tile code and retreave the image i need to use a quad batch.
this has a few added advantages all my tiles are in one place meaning that to update them i just loop through and update the tiles. Updateing the tiles at this moment is only for tiles that are animated ( all water tiles for instance allways animate at the same time and the same image ).
The second of which is you save lots of Memory only having one instance in this fashion.
Now just incase you were insterested in having some kind of differnce in your tiles ( eg the same tile but differnt frames ) you could i suppose store a meta value in the tile class and uses an index into an array to from the from data stored with the tile ID
this way you can animate tiles at differnt frames and or based on differnt situations.
At anyrate the more data you need to update in regards to a tile map means more overhead
foreach loops alone kind of seem like a bottle neck with my current setup
Some test data for times
My quad tree retreaves data for the game map and this takes up to 1ms ( the tree actually has a cache of sorts from the last query )
the actual drawing code itself which uses foreach loops because they are faster then for loops takes about 10 to 11 ms, thats for a 800 by 600 screen with a 32 by 32 tile.
In DEBUG build at the 800 by 600 resolution i get 60 fps pritty stabaly and at full screen which is somthing around 1320ish (can't remember the exact resolution i am on and i am to lazy to look it up) by 720 i net about 35 to 40 fps roughly..
In release mode i get 60 fps on both and my settings are for 60 fps.
As a special side note since i use a quad tree it is possible to get back multiples of the same sector on the case that the sector resided on a dividing boundary this is fixed by have a flag for weather or not the sector has already been touched ( eg has allready been added to the list to return ) and that flag is reset after drawing.
Well not saying its perfect there may be better ways of doing it but at anyrate maybe it will at least spawn an idea for you.