What Byte56 says makes sense.
I'm not sure why you need 2 separate coordinates (chunk coords and xy coords). But since a map is always square, the most basic representation is a 2D array of ascii chars
So there is the specification of a 4x10 map in 40 bytes. A 10,000 x 10,000 map would take 95MB, which isn't that bad. Because of the repetition, simple compression using zlib would probably reduce the size a lot.
To make this work, you can merge the information of tile-type and walkability together. So
@ is an impassible tree, for example, and
. is (passable) grass, and
, is (passable) dirt. The world space coordinates of each tile is implied, as each "chunk" here is a fixed size (say 1 world unit x 1 world unit). The bottom left corner of the world could be placed at 0,0.
Using single characters means each tile can represent one of 255 different things. If you want 65,536 different things represented, you could use unicode. If you want more, you could use UTF-32.
To add in items, and NPC's you could use an item layer.
. means empty and
$ means money.
You probably could store the map size and some kind of "key" as to what each character means in the header of this map file format.