...

I was just reading RFC1034 about DNS, and one thing I noted was that there is a "reverse lookup" feature. [....] The RFC did not make it very clear how this is done. Does this use a "flat" database?

No. Its fully distributed. The fact that networks are assigned in heirarchical chunks should explain how its done, and why the bytes get reversed for the lookup. As an example, MIT owns network 18, which is to say that all MIT addresses are 18.XXX.XXX.XXX, and 18.IN-ADDR.ARPA is a server at MIT. MIT may have sub-servers beyond that level, but DNS makes us oblivious to this.

Of course, that's more useful for MIT, which owns Network 18, than for the thousands of people on networks 192.xxx.xxx; reverse lookups don't seem as reliable for Class C. On the site I run, I implement reverse lookups for my subnet, and the folks who run our larger internal net have pointers that know how to find it. But DNS would work for forward lookups even if the reverse weren't maintained, or deliberately omitted some parts for security/predictability reasons.