Two replicas of the same dataset, each holding a million records, need to find out whether they agree. The honest way is to compare every record: fetch both copies, walk them in the same order, check each pair, and report the first place they differ, or the thousandth. That works, and it's also the answer nobody wants, because it means moving a million records' worth of data across a network just to learn that 999,998 of them were already identical. What's actually needed is a way to compare two large things and get back, cheaply, one of two answers: "these are exactly the same," or "these differ, and here specifically is where" — without reading, hashing, or transmitting the parts that already agree. A single hash of the whole dataset gets the first half for free: hash both copies, compare the two hashes, and a match proves equality without reading anything twice across the network. But a mismatch tells you nothing about where the difference is — it could be one byte in one record, or it could be everything, and a single hash collapses both possibilities to the same signal. The single hash answers "same or different." It cannot answer "different where." A Merkle tree is what you build when you need the second answer at a cost that scales with the size of the difference, not the size of the dataset.
The construction is a binary tree, built from the bottom up. Split the data into blocks — records, chunks of a file, whatever the natural unit is — and hash each block individually; these become the leaves. Then pair up adjacent leaf hashes and hash each pair together, producing one parent hash per pair; do that again one level up, and again, until a single hash remains at the top: the root. Every hash above the leaf level is a hash of hashes, not of the original data directly, but it still depends on every leaf beneath it, transitively — change one byte in one block, and that block's leaf hash changes, which changes its parent's hash, which changes that node's parent, all the way to the root. The root hash is therefore exactly as sensitive to any single-byte change anywhere in the dataset as the naive whole-dataset hash was — comparing two roots still answers "same or different" with the same certainty a flat hash gives. What's different is that the tree didn't throw away the intermediate hashes on the way to the root, and those intermediate hashes are what make the second question answerable.
Comparing two Merkle trees for a difference means comparing root hashes first. If they match, stop — the entire dataset is identical and nothing else needs to be touched. If they don't match, the two sides exchange the pair of child hashes one level down instead of the whole dataset: two comparisons instead of one, but each one narrows the search by half. Whichever child pair disagrees gets expanded one level further, and the pair that agrees is dropped from consideration entirely — nothing beneath an agreeing pair is ever fetched, hashed again, or transmitted, because the hash already proved everything under it is identical. This repeats, level by level, until the mismatch is chased all the way down to the specific leaf blocks that actually differ. For a balanced tree over n blocks, this takes on the order of log n comparisons to locate a single differing block, against n comparisons for the naive approach — and, more importantly for real network use, it costs O(log n) data transmitted along the way, not O(n). The savings scale with how much of the two datasets already agree: two nearly identical million-record replicas that differ in one row cost a Merkle comparison about twenty hash exchanges to pinpoint; they'd cost a full linear scan a million.
Git's own object model is a Merkle tree, and it is worth naming plainly rather than gesturing at: a commit points to a tree object, a tree object points to blobs and other trees by hash, and the commit's hash depends on all of it transitively — which is the exact mechanism behind the claim, made in an earlier piece here, that changing anything in this repository's history changes every commit hash after the change. That claim was really a Merkle tree claim, stated without the name. Cassandra and DynamoDB use Merkle trees for anti-entropy repair between replicas: instead of streaming an entire partition to compare it against another node's copy, each replica builds a tree over its data and the two exchange hashes top-down, transferring actual rows only for the specific ranges whose hashes disagree. Certificate Transparency logs use a Merkle tree so that a browser can get a short cryptographic proof — a handful of hashes, not the whole log — that a specific certificate is included in a log containing millions of entries, without downloading the log to check. Bitcoin uses one to let a lightweight client verify a transaction is in a block by checking a short path of hashes up to a root it already has, instead of downloading every transaction in that block. In every one of these, the shape of the problem is the same: a large, mostly-static structure, a need to verify or locate a small change within it, and an unwillingness to pay a cost proportional to the whole structure just to find or confirm something small.
The efficiency depends on the two sides agreeing, in advance, on how the data is chunked into leaves and in what order the tree is built — a Merkle tree computed over the same million records but split into different-sized blocks, or in a different order, produces a different tree with no comparable structure, even though the underlying data might be identical. This isn't a flaw so much as a precondition that's easy to overlook: the two sides need a shared, deterministic scheme for turning data into leaves before the tree's hashes mean anything comparable to each other. Rebalancing also has a cost that's easy to underestimate — insert or delete one record in the middle of an ordered dataset and, depending on how leaves are defined, every leaf hash after that point can shift position, which can force recomputing a much larger share of the tree than the size of the actual edit would suggest, unless the chunking scheme is designed around content boundaries rather than fixed positions specifically to avoid that. And a Merkle tree, like the flat content hash it's built from, proves agreement or locates disagreement — it says nothing about which of two disagreeing copies is the correct one, or whether either is. That question belongs to whatever process decided the data should look a certain way in the first place, not to the hashing scheme that compares two claims about it after the fact.