Imagine transmitting the entire DNS by broadcast one-way satellite links, on several channels. On one group of channels you transmit simply everything, in a rotating fashion, in order to populate a DNS cache. On a second channel group, you transmit all the frequently-used stuff only, otherwise it's the same as the first. On a third group of channels, you transmit all the updates as they happen. One final channel group, group four, has only one channel in it and duplicates of all the group three content combined into a single channel.
Each channel is very highly compressed, and is pre-sorted so that delta compression could be one of the early compression layers. After every so-many records, the stream of data has to be broken up in such a way that a listener can synch up with the compression scheme and get into understand it having only missed a certain number or seconds worth of entries before they hear a synchronisation symbol followed by enough info to get them started with the compression scheme
When you first become a client, you listen to as many channels in group two as you have radios, in order to get up and running with something useful as quickly as possible. If you have even more radios, you listen to group one channels as well, otherwise you switch to absorbing group one after group two. Group two content is not duplicated in group one, it is simply omitted silently, so a new client always has to listen to all of both channel groups eventually.
The groups one to three are partitioned so that a channel in a group only carries a known part of the DNS, which increases the speed of rotation, and allows faster startup time if you have multiple radios. A fast, cheap hash function tells you which channel in a group a particular domain name will be mentioned on. Info with a list of parameters to the hash function and a map of the set of channels are transmitted on every channel frequently. Each channel simply rotates, it starts transmitting again from the beginning when it gets to the end of the data.
This partially completed design has some outstanding problems, the main one currently being the synchronisation between group one and group three / four content. Including some data in group three that is slightly old - but how old? - bridges the gap between the intialisation-time ‘full’ database and the live updates’ stream. Actually though, getting it wrong is not critical, because this is only a cache and being incomplete simply means that an attached normal DNS server has to consult the real live DNS more often. Also, without an estimate of database sizes and channel throughput I don't know if this plan is useful or even feasible. Neither do I know what the rate of DNS updates is, so I don't know whether channel four might be able to keep up with the rate of change of the entire world.
If the numbers are too large however, I could always simply reduce the scope of problem, and deal with only part of the database, such as the well-known TLDs plus one or more ccTLDs.