Sometime between the start and the end, there's often a mandatory burn it all down step required to more fully satisfy either (2) or (3). Watching hundreds of MB of data getting written to my HD for an apt-get update makes me 90% certain that Debian indeed needs to burn it all down.

To their credit, they started really early. And burning it all down seems to be an increasingly better option for purely extrinsic reasons; the late mover advantage keeps increasing, and better and better options keep emerging. A LMDB-based refactor perhaps? This is probably a pipe dream, alas: Debian developers must have a hundred different programs that all build and extend forward the original "make it work" technology, to make it survivable. And that's really my final counter to your cute linear notion of ongoing improvement: the mold is set, and there are dozens of things bound up in what has happened.

Where do you want LMDB? apt has a super fast binary cache, the repositories and dpkg store their package lists as text files.

RPM systems have the advantage IIRC that they can basically just download a bunch of sqlite3 databases, which means they do not have to parse any data.

AFAIK RPM uses BerkeleyDB, though it will probably switch to LMDB https://bugzilla.redhat.com/show_bug.cgi?id=1086784

> implying apt is a young tool and the maintainers didn't have many years to go from 1 to 3

According to the developer the bug was present only in the 1.1 series, which is just a few months old (it was pre-released at debconf 2015, and is not in Jessie if i'm not mistaken).

Furthermore pdiffs were introduced in ~2006: https://www.debian-administration.org/article/439/Avoiding_s...