In nutiteq mobile maps SDK (later Carto, now abandonware) we used specifically compressed bitmap to represent 'water' and 'empty land' tilemasks to cover these two special cases. We provided planet-scale mobile embedded mbtiles package in 30GB if I remember well. This tile mask (quite instant bitmap index) concept should work well for server case also.
The Linux kernel's filesystem cache is actually really efficient at doing this. I doubt we could come up with a nginx scripting solution which could be equally efficient.