Version-controlled databases using Prolly trees

By Daroc Alden May 1, 2026

Modern database and filesystems make pervasive use of B-trees, which are tree structures optimized for storing sorted lists of keys and values on block devices. Dolt is an Apache 2.0-licensed project that makes clever use of a variant of a B-tree to support efficient version control for an entire database. The data structure it uses could well be of interest to other projects.

The company behind Dolt, DoltHub, makes its money selling hosted versions of three Apache-licensed open-source projects: Dolt, Doltgres, and DoltLite. The projects are intended to be drop-in replacements for MySQL, PostgreSQL, and SQLite, respectively. They have separate frontends for the different SQL dialects, but the projects share a common storage backend that supports version-control operations.

In practice, that allows the projects to expose Git-like operations as custom SQL functions:

    -- Modify the database
    INSERT INTO users VALUES (...);
    -- Add the changes to a table to staging
    SELECT dolt_add('users');
    -- Commit them
    SELECT dolt_commit('-m', 'Add Joe to users');
    -- See the resulting diff
    SELECT * from dolt_diff_users('HEAD~1', 'HEAD');

At any given time, the database has a current HEAD commit, some number of changes in the staging area, and some number of changes in the working area, just like Git. That deliberate similarity is a major selling point of the projects — the company's home page says: "You already know how to use Dolt." That may be an exaggeration, but it is true that having basic knowledge of Git and SQL seems sufficient to start making use of Dolt.

What might be less clear is what one would use a version-controlled database for. Simply making commits on its own does not really add much power over the existing concept of a database transaction. The real utility of Dolt comes from the ability to restore old commits, fork historical states of the database, and merge in changes after review. For example, a programmer might want to run an analysis against an old state of the database to determine what would have been reported as of a particular date. They could make a new branch pointing at a historical commit, cherry pick a schema change that the analysis needs, and then run it.

Another potential use is to give automated tools a "real" database that they can work against, without giving them the ability to completely break the production database; any changes can be investigated separately and merged in only once it is clear that they won't break anything. Dolt is fully compatible with normal MySQL clients; the only difference is in the connection string, so the tools have no reason to think that they're not talking to the real production database.

    -- Connect to the normal db
    mysql://db-server:3306/mydb
    -- Connect to a named branch
    mysql://db-server:3306/mydb/branch-name
    -- Connect to a read-only historical commit
    mysql://db-server:3306/mydb/ia1ibijq8hq1llr7u85uivsi5lh3310p

Of the three projects, Dolt is the most mature. Doltgres recently entered beta, and DoltLite is somewhere in-between — the components adapted from SQLite have had plenty of testing in their original context, but the project is still on version 0.8.1. The company's performance testing of Dolt suggests that its speed is comparable to MySQL's, although the normal caveats about the difficulty of precise benchmarking apply.

That competitive performance is possible because Dolt only changes the storage layer of the database. The query planner, index maintenance, and so on all reuse MySQL, PostgreSQL, or SQLite's existing implementations. All of these databases use B-trees; Dolt uses a slight variation on a B-tree that allows efficient diffing and shares storage between mostly identical versions.

B-trees

B-trees have a lot in common with their simpler cousins, binary trees. In a binary tree, each node has a key, a value, and two (possibly empty) sub-trees. Keys with a lower value are stored in the left sub-tree, and keys with a higher value are stored in the right sub-tree. As long as some scheme is employed to keep the tree balanced (such as the use of red-black trees in the kernel), this results in reasonably efficient comparison-based searching: each comparison cuts out roughly half of the remaining candidates. Keys are looked up in time proportional to the base-two logarithm of the number of nodes in the tree.

B-trees take this core concept, and remove a bunch of pointer indirections. Each node in a B-tree has an array of keys, values, and pointers to sub-trees. Typically, the size of the array is chosen such that one node fits on one sector or page of the underlying storage. To find an item in a B-tree, the computer scans over the array and either finds the key directly, or finds two keys that the target key should be between, and goes on to check the corresponding sub-tree. This structure greatly reduces the number of levels of the tree and the number of pointer indirections, thus making the whole structure faster to access in practice. In a B-tree with sixteen keys per node, for example, searching for a key only involves one quarter of the number of nodes compared to a binary tree.

This makes B-trees an excellent fit for databases, which have to maintain a balance between efficient searches for particular items, in-order scans over the items in a range, and access to the underlying storage. There are a handful of variations of B-trees used by different databases that provide small speedups. For example, moving all of the values to leaf nodes and storing only keys in the interior nodes of the tree allows for more keys per interior node, making the tree wider and shorter. An extension to that idea adds a "next" pointer to each leaf node so that in-order traversals can proceed along the leaves without needing to load any interior nodes. Dolt's core data structure, described below, incorporates both of those optimizations.

The problem with plain B-trees, and the reason that Dolt is interesting, is that comparing entire B-trees is expensive. The order in which items are inserted and deleted can affect how the internal nodes of the B-tree are structured, which means that the only way to compare two B-trees is by iterating through both trees in their entirety. That downside doesn't matter much to traditional databases, but it poses real problems for version-control systems.

Snapshot-based version-control systems, such as Git, can be thought of as storing many snapshots of some source tree. Each commit is logically independent, and could in theory just be stored as-is. In practice, most Git repositories do not completely change between commits, and it's more efficient to store the differences between subsequent snapshots, rather than the snapshots themselves.

Git, which works with entire directory trees, relies on being able to quickly check whether a particular sub-tree has changed in order to produce compact diffs that include only the actual changes. B-trees aren't compatible with that kind of algorithm, since the same logical list of keys and values could be represented by two different B-trees. Naively applying a diff algorithm to a B-tree could produce a lot of inefficient churn between representations of internal nodes.

The problem comes from the way that B-trees split and merge nodes as items are added and removed. When a B-tree node is full, it is split into two smaller nodes that are each half-full. When a B-tree node is not full enough (a threshold that varies between implementations, but which is typically just under half-full), its children are merged together to produce a more full node. When correctly implemented, this keeps the B-tree balanced and prevents the nodes from wasting storage space. But it also means that splitting and merging decisions depend on the order of insertion into the tree.

Prolly trees

Probabilistic B-trees (Prolly trees, for short) are Dolt's answer to this problem. They are almost identical to B-trees, except that the logic for inserting and removing items is updated such that any two trees that contain the same items are completely identical regardless of how items were inserted. The same property holds for individual sub-trees, so comparing two Prolly trees is much simplified: if a sub-tree hasn't changed between two versions, it will have the same hash, even if an item was inserted and then removed.

To accomplish this, Prolly trees need to be able to determine what size each node "should" be, based only on its contents and not on any internal state of the tree. At first, it might seem tempting to say that every node should be as full as possible, to maximize use of storage space. But that would require sometimes shuffling nodes at the same level of the tree back and forth between parents, which would destroy some of the nice properties of the B-tree and cause additional churn between versions. To keep insertion and deletion efficient, the average node should not be so full or so empty that the insertion or deletion of a single item will need to trigger a split or a merge.

The solution to this problem is to use a hash function to make the decision in a way that depends only on the data and not on how full a particular node happens to be. A hash is effectively a deterministic pseudorandom number that can be compared to a threshold to make a randomized decision, which is where the "probabilistic" part of Prolly trees comes in. To insert a new value into a node, the implementation puts it in the correct position in the array (based on the key), and then recalculates where the boundary between this node and its sibling should fall based on the hashes of the items. Each hash is compared to a chosen cutoff value (the threshold) to decide whether the node should end at that item. Since the values of the hashes are independent, so are the decisions about where to put the boundaries between nodes. Most of the time, therefore, adding an item won't result in a new boundary: its hash value will be above the threshold, and the node will still end at the same place (a preexisting item with a low hash value). Occasionally, an inserted item will have a low hash value, causing the node to split in two and keeping the overall sizes of the nodes balanced.

That picture is slightly complicated by performance considerations; in order to keep the nodes optimally sized, the threshold used is actually dynamic, based on the number of items before a given key in a node. That still means that the actual decisions about where to place the boundaries between nodes are made independently of the pre-existing structure of the tree. The locations of the boundaries depend only on the hashes of the items stored in the tree, which are the same regardless of what order items were inserted in.

This insertion logic is a little complicated, especially if the implementation is optimized for performance, but it's still reasonably compact:

    # Unoptimized Python example code
    # This function is called by some internal node to update one of its child
    # nodes; the return value is used to update the internal node.
    def insert_into_node(node, new_items):
        sibling = node.next_sibling
        new_items = sorted(new_items + node.items)
        collected = []
        nodes = []

        while new_items:
            next = new_items.pop(0)
            collected.append(next)
            if hash(next.key) < threshold(len(collected)) \
               or len(collected) >= max_node_length:
                nodes.append(Node(items=collected))
                collected = []

        if collected:
            # The while loop didn't end on a natural barrier
            if node.next_sibling is not None:
                new_nodes, sibling = insert_into_node(node.next_sibling, collected)
                nodes += new_nodes
            else:
                nodes.append(Node(items=collected))

        for i in range(1, len(nodes)):
            nodes[i - 1].next_sibling = nodes[i]
        nodes[-1].next_sibling = sibling

        return nodes, nodes[0]

With a suitably chosen threshold, the average insertion won't create a new node, and so only one node needs to be updated at each level of the tree. Theoretically, adding a single item could cause all of the nodes after it to be split up differently, but the chances of that are infinitesimal, because the hash values of the items are statistically independent. The hash values of all of the existing items would have to just barely miss the threshold in order to cause that kind of realignment, so it's not a practical performance problem. Since the decision of how to place items into nodes only depends on the data, the same nodes will be created every time.

There are some downsides to using a Prolly tree over a B-tree. For example, nodes need to store the hashes of sub-trees, which requires either more storage space or an additional indirection through a content-addressed block store to turn a hash into an address. Content-addressed storage is a scheme that many version-control systems use to deduplicate data: a particular diff or other object is stored in a location based on the hash of its contents. This ensures that duplicate items will reuse the same storage space. A Prolly tree implemented as part of a version-control system can reuse that existing content-addressed object storage for blocks, and refer to blocks by hash, leading to more compact internal nodes. Other systems will need their own solutions.

Another problem is that the performance of the tree is highly sensitive to how the probabilities of splitting are tuned. Using a constant probability results in the mean node being half-full, but the median node containing only one or two entries. To cope with that, Prolly trees use a dynamic threshold that increases as the node fills up, so that the size of nodes ends up following a normal distribution. Of course, some applications really do have requirements for worst-case performance rather than average-case performance, which is incompatible with the randomized layout of a Prolly tree.

Despite these deficits, Prolly trees could be a useful data structure for applications that depend on being able to compare snapshots of trees, or on being able to store trees in a content-addressable way.

History and future

Prolly trees were invented by Aaron Boodman for the now-defunct Noms database. Afterward, they were picked up by the InterPlanetary Linked Data project and by DoltHub. The storage backend used in Dolt is a forked version of Noms, although the project has seen a fair number of changes and optimizations since then. Some other implementations of Prolly trees exist as libraries, but none apply them to databases.

Dolt provides an appealing evolution on the traditional design of a database. Personally, however, I am excited to see how the ideas could apply in other programs that use B-trees, such as filesystems. Prolly trees are certainly not appropriate for all uses of B-trees, but filesystems share many of the same tradeoffs between in-order traversal, random access, and ease of snapshotting that databases do. Perhaps Prolly trees could help with space-efficient snapshots of large, frequently modified files.

---

G-trees

Posted May 1, 2026 21:26 UTC (Fri) by daroc (editor, #160859) [Link]

Susceptible to hash-flooding?

Posted May 2, 2026 12:07 UTC (Sat) by Karellen (subscriber, #67644) [Link] (4 responses)

Theoretically, adding a single item could cause all of the nodes after it to be split up differently, but the chances of that are infinitesimal, because the hash values of the items are statistically independent.

This set off my spidey-senses for hash flooding which might provide a way to trigger this intentionally, given that one could be storing externally-provided data in the database. But I'm pretty sure the depth of understanding I've got from the article (as good as it is) isn't enough to tell whether that could be a concern here? Is it, and if so, are there any mitigations (seeding?) that might be available?

Susceptible to hash-flooding?

Posted May 2, 2026 13:23 UTC (Sat) by daroc (editor, #160859) [Link]

Susceptible to hash-flooding?

Posted May 2, 2026 13:52 UTC (Sat) by Wol (subscriber, #4433) [Link] (1 responses)

Susceptible to hash-flooding?

Posted May 3, 2026 12:41 UTC (Sun) by Karellen (subscriber, #67644) [Link]

I notice that hash flooding appears to be a cryptographic thingy. So its application and threat to a database is likely low.

Kind of - I remembered it more being applicable to hashmaps/dictionaries provided by programming languages and runtimes. While they may use a reasonable (even cryptographic) hash internally - which is why flooding is grouped with cryptographic hash attacks on Wikipedia - which was resistant to worst-case behaviour with random data, there were circumstances where it wasn't that hard to select malicious data to deliberately trigger it if an attacker knew how the hash was being used.

Good to get an opinion that it's unlikely to be an issue though, thanks.

Susceptible to hash-flooding?

Posted May 3, 2026 21:15 UTC (Sun) by ballombe (subscriber, #9523) [Link]

Dolt is LLM slop, though

Posted May 2, 2026 18:51 UTC (Sat) by mirabilos (subscriber, #84359) [Link] (2 responses)

Dolt is LLM slop, though

Posted May 4, 2026 10:39 UTC (Mon) by t0 (subscriber, #171761) [Link] (1 responses)

Yes, and their blog (dolthub.com/blog/) mentions the "Gas Town" project. That is for hardcore LLM fanatics. The author of Gas Town, Steve Yegge initially built his own version-controlled DB, saying:

"In October, I told Claude in frustration to put all my work in a lightweight issue tracker. I wanted Git for it. Claude wanted SQLite. We compromised on both, and Beads was born, in about 15 minutes of mad design."

But they later moved to Dolt for this issue tracker purpose.

Dolt is LLM slop, though

Posted May 5, 2026 23:29 UTC (Tue) by Paf (subscriber, #91811) [Link]

Rationale for the pseudo-random threshold?

Posted May 5, 2026 13:28 UTC (Tue) by marcH (subscriber, #57642) [Link] (8 responses)

Rationale for the pseudo-random threshold?

Posted May 5, 2026 14:54 UTC (Tue) by Wol (subscriber, #4433) [Link] (7 responses)

Rationale for the pseudo-random threshold?

Posted May 5, 2026 22:12 UTC (Tue) by marcH (subscriber, #57642) [Link] (6 responses)

Rationale for the pseudo-random threshold?

Posted May 6, 2026 7:00 UTC (Wed) by daroc (editor, #160859) [Link] (5 responses)

Rationale for the pseudo-random threshold?

Posted May 6, 2026 14:05 UTC (Wed) by Wol (subscriber, #4433) [Link] (4 responses)

Rationale for the pseudo-random threshold?

Posted May 6, 2026 15:52 UTC (Wed) by farnz (subscriber, #17727) [Link]

While a good hash should have a flat distribution across all possible inputs (because all output values are equally likely), it should not have a mode at all (since all values are equally likely), and thus will not form Gaussian noise automatically (the form of noise that gives you a bell curve, where the mode is well-defined and equal to the mean). Instead, the distribution of noise you get by using a hash function is an artefact of the data you supplied to the hash function; for non-adversarial inputs (e.g. where you've keyed the hash so an attacker can't control the input to the hash function), the mean should be approximately half the maximum value, but the distribution is still unknown.

Because the hash distribution is an artefact of the input data, you need some way to ensure that an unfortunate distribution of hashes won't result in nodes that are consistently too large or too small. The simplest way to do this reliably is to vary the threshold for the next node split point based on the size of previous nodes - if the average node so far has been too small, adjust the threshold to get larger nodes in future, while if the average node has been too large, adjust the threshold to get smaller nodes in future.

More complex strategies also exist for setting the threshold - I've not looked to see how Dolt handles this - but the key to why you need a varying threshold is simply that the shape of the distribution of hash values is unknown.

Rationale for the pseudo-random threshold?

Posted May 6, 2026 15:56 UTC (Wed) by daroc (editor, #160859) [Link] (2 responses)

Rationale for the pseudo-random threshold?

Posted May 6, 2026 23:01 UTC (Wed) by Wol (subscriber, #4433) [Link] (1 responses)

Rationale for the pseudo-random threshold?

Posted May 15, 2026 19:33 UTC (Fri) by zachmu (guest, #183605) [Link]

Dolt contains no MySQL code

Posted May 15, 2026 19:00 UTC (Fri) by zachmu (guest, #183605) [Link]

Nice article, but a small correction: Dolt is not a fork of MySQL and contains no MySQL code. It's a completely new implementation from the ground up, both the storage layer and query engine. Similarly, Doltgres is not a fork of Postgres and contains no Postgres code. The query engine for both databases is go-mysql-server, and they both use storage and version control libraries implemented in the Dolt project.

DoltLite is different: it's a fork of SQLite3 with the storage engine ripped out and replaced with a prolly tree implementation.

There's also a fourth variant that's even newer: DumboDB. It implements the dolt version control operations in a Mongo-compatible document database. Like Dolt and Doltgres, it contains no mongo code. It's a new implementation.

Dolt's implementation of prolly trees did indeed originate with Boodman's noms project, but similar concepts in other domains date back to at least 2009 by our research and there are probably even older ones. Like many inventions, prolly trees have a long history with many contributors, and people continue to re-invent the concept independently. See this blog for more background.