Post

What do Git, Cursor, and Dynamo have in common? Merkle trees! A great data structure for tracking file changes, facilitating incremental sync with remote servers. Say we want to track changes to a codebase at a per-file level. We compute a hash for each source file, and these become leaf nodes.

5/1/26, 2:37 pm0 reposts5 likes

Ben

@benjdd.com

5 Jan

We then build a tree based on the directory structure. A parent node's hash is a hash of the concatenation of all its children's hashes. Inner nodes' hashes are based on the data / hashes of its descendants. This culminates in the root node, whose hash is based on ALL the tracked source files.

Ben

@benjdd.com

5 Jan

When syncing local file changes with a remote server (like Git) we can quickly tell if changes were made by comparing the client's root hash to the server's. If they differ, the tree is navigated to find the leaf node(s) with changes, and only those files need to be re-synced.

Ben

@benjdd.com

5 Jan

This makes for fast change detection (O(log n)), and saves bandwidth since we only need to re-sync files that we know have been modified.