← Back to context

Comment by Zamicol

4 years ago

I've not heard the term "probabilistic tree" and I've having difficulty pulling up references. I suspect it's implemented by subpackage ptree[0]. Could you explain what makes probabilistic trees different from hash tables or other similar data structures?

[0] https://github.com/gotvc/got/tree/master/pkg/gotkv/ptree

5 comments

Zamicol

Reply
brendoncarroll  4 years ago

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.

vnorilo  4 years ago

I was thinking of treaps;

https://en.m.wikipedia.org/wiki/Treap

  • hinkley  4 years ago

    Some, but not all, treaps have a node weight that is updated in a probabilistic fashion. The act of balancing the tree is still deterministic, but the weights of each node are randomized.

    I keep trying to find a use for treaps, but haven't had a project that needed it. In particular, the value of a balanced tree is in consistent cost of lookups for arbitrary elements. But if you are mixing entries that are accessed often with those that are not, having an 8:1 access time ratio between the two would be a feature not a bug.

    • vnorilo  4 years ago

      I used a persistent treap for a lock free priority queue (swap in a new root at insertion). It felt nice but to be honest, didn't do a comprehensive comparison to alternate implementation strategies.

      edit: looks like at least one other has has the same idea https://github.com/lthibault/treap