Yeah with snappy they probably could get like 30% savings (I bet domains don't compress well) without much more cpu usage.
Alternatively a btree somehow they can take advantage of prefix compression
Ah yes, something like prefix tree would work well storing reverse domain names like com.abc.www (although this is such a well known thing I feel like I must be missing things).
Definitely. Even a custom compression/encoding that knows to treat the different fields differently -- just a 4-byte binary IP address for A records, normal LZ-based text compression of the domain name (perhaps using a custom starting dictionary and/or Huffman table), etc.