Merkle-boom (DB)
Een hashboom waarin elk blad de hash van een databereik is en elk knooppunt de hash van zijn kinderen. Twee replica's kunnen zo van boven naar beneden precies vaststellen waar ze verschillen, zonder alle data te versturen.
Werking: de wortel vat de hele dataset samen in één hash. Zijn de roothashes van twee replica's gelijk, dan zijn ze identiek en is het klaar. Zo niet, dan vergelijk je de hashes van de kinderen en duik je alleen in de takken die afwijken, zodat je de afwijkende bereiken in logaritmische tijd vindt in plaats van rij voor rij te vergelijken. In gedistribueerde databases (Dynamo, Cassandra, Riak) vormt dit de basis van anti-entropy en repair. Dezelfde structuur komt voor in Git (commits), blockchains (transactieverificatie), Certificate Transparency en IPFS: overal waar grote datasets efficiënt gecontroleerd of vergeleken moeten worden. Een van de veelzijdigste datastructuren in gedistribueerde systemen.