This is from 2022. It is based on Noms [1], which is no longer maintained (they forked it).<p>I think the Noms doc linked from this article [2] is clearer than the article itself. That said I sill cannot turn my head around to grasp how this entire thing work tbh. I hope they wrote a peer reviewed paper to serve the audience better.<p>[1] <a href="https://github.com/attic-labs/" rel="nofollow">https://github.com/attic-labs/</a><p>[2] <a href="https://github.com/attic-labs/noms/blob/master/doc/intro.md#prolly-trees-probabilistic-b-trees" rel="nofollow">https://github.com/attic-labs/noms/blob/master/doc/intro.md#...</a>
I really wonder what the memory overhead of the prolly tree is.<p>Using hashes as links isn't cheap especially with sha-512 wide hashes (I think they use 20bytes in reality?).
I'd estimate their fanout at between 50-200, which isn't that much either.<p>So my feeling is expensive nodes, combined with low-ish fanout => high cost of storage?