Merkle tree (DB)
A hash tree where each leaf is a hash of a data range and each node a hash of its children. It lets two replicas find exactly where they differ by comparing hashes top-down — without sending all the data.
Mechanic: the root summarizes the entire dataset in a single hash. If two replicas' root hashes are equal they're identical (done). If they differ, you compare the children's hashes and only drill down into the branches where they diverge → you locate the diverging ranges in logarithmic time instead of comparing row by row. In distributed databases (Dynamo, Cassandra, Riak) this drives anti-entropy/repair. The same data structure is used in Git (commits), blockchains (transaction verification), Certificate Transparency, and IPFS — everywhere you want to efficiently verify or compare large datasets. One of the most versatile data structures in distributed systems. Related to anti-entropy and consistent hashing.