Merkle-Baum (DB)
Ein Hash-Baum, bei dem jedes Blatt der Hash eines Datenbereichs ist und jeder Knoten der Hash seiner Kinder. Damit finden zwei Repliken genau die Stelle, an der sie sich unterscheiden, indem sie Hashes von oben nach unten vergleichen — ohne alle Daten zu übertragen.
Mechanik: Die Wurzel fasst den gesamten Datensatz in einem einzigen Hash zusammen. Sind die Wurzel-Hashes zweier Repliken gleich, sind sie identisch (fertig). Unterscheiden sie sich, vergleicht man die Hashes der Kinder und bohrt nur in den abweichenden Zweigen weiter → man findet die divergierenden Bereiche in logarithmischer Zeit, statt Zeile für Zeile zu vergleichen. In verteilten Datenbanken (Dynamo, Cassandra, Riak) treibt das Anti-Entropy/Repair an. Dieselbe Datenstruktur steckt in Git (Commits), Blockchains (Transaktionsverifikation), Certificate Transparency und IPFS — überall dort, wo man große Datenmengen effizient verifizieren oder vergleichen will. Eine der vielseitigsten Datenstrukturen in verteilten Systemen. Verwandt mit Anti-Entropy und konsistentem Hashing.