Merkle-träd (DB)
Ett hash-träd där varje löv är en hash av ett dataintervall och varje nod en hash av sina barn. Låter två repliker hitta exakt var de skiljer sig genom att jämföra hashar uppifrån och ned — utan att skicka all data.
Mekanik: roten sammanfattar hela datamängden i en enda hash. Om två replikers rot-hashar är lika är de identiska (klart). Skiljer de sig, jämför man barnens hashar och borrar bara ned i de grenar där de avviker → man lokaliserar de divergerande intervallen i logaritmisk tid i stället för att jämföra rad för rad. I distribuerade databaser (Dynamo, Cassandra, Riak) driver detta anti-entropi/repair. Samma datastruktur används i Git (commits), blockkedjor (transaktionsverifiering), Certificate Transparency och IPFS — överallt där man effektivt vill verifiera eller jämföra stora datamängder. En av de mest mångsidiga datastrukturerna inom distribuerade system. Hör ihop med anti-entropi och konsistent hashing.