A pretty neat way to store heightmaps (or audio waves) in a lossless but compressed manner is to take two points and only store the offset between them in the smallest possible data type, then going to the next point and store its offset and so on. If you know that most values will be the same, you can also store the range in which the offsets are going to be zero.
Obviously this is pretty simple (but pretty much the same way most lossless audio codecs work, on a very high level), and you can do some more tricks when you work with a spacial grid, but that should get you started.
Edit: To store them efficiently, you can create a hash out of the tiles position and store it either in a big hashtable (probably not a good idea because rehashing on disk is quite expensive), or use the filesystem itself as hashtable and the name of the filestream as hash. The filesystem is quite good at fetching named resources, so that's not going to be a huge problem. Also, because I'm a lovely person, here is a hashing function that has no collisions for +-10k tiles in every direction (I bruteforced the correct prime numbers myself and also tested that there are no collisions):
#define P1 1149851
#define P2 1860498
#define P3 87403803
#define P4 1568397607
#define P5 3010349
unsigned int getChunkHash(int x, int y)
{
unsigned int h = (x * y) + P5;
h ^= x < 0 ? x * P1 : x * P2;
h ^= y < 0 ? y * P3 : y * P4;
return h;
}
