Comment by brendoncarroll

Yep, your link is indeed to the probabilistic tree used in GotKV.

Here "probabilistic" just refers to a way of balancing a tree. Rather than having a set of rules to keep the tree balanced, like with a btree or red-black tree, balancing decisions are made pseudorandomly. The result is that the tree is very likely to be balanced, and is unlikely to be unbalanced.

In the case of GotKV's tree: the entries are stored together in a stream, and for each entry a hash is computed. If that hash is lower than a certain value then the entry is considered a split point, and a tree node is created. So now we have a stream of entries, divided probabilistically into sections. Each section is a tree node. Now take references to those nodes and turn them into entries, and repeat the process, so you have fewer nodes. That continues until you have one node, which is the root. This technique is very similar to content defined chunking, and some probabilistic trees are implemented using content defined chunking on their record format, rather than a pseudorandom value calculated per entry, as in GotKV.

For those unfamiliar with probabilistic data structures, I highly recommend trying to understand skip-lists first. At least why they are balanced.

https://en.wikipedia.org/wiki/Skip_list

As an aside, one of the neat things about GotKV is that the keys are delta-encoded. Adding or removing a prefix from every key in the tree is a constant time operation. This might be obvious to some of the database folks out there, but it's a fun mind-blower if you haven't encountered the technique before.