It took a long time, but the incremental insert for a Prolly Tree is finally done. I don't think I've ever spent this long as such a little part of code. The two aspects that had me struggling were the bottom-up breadth-first traversal, and how to replace the swath of

The punchline first: the incremental insert is finally done on the Prolly Tree. I don't think I've ever spent so much time on such a small, core piece of code. It was also a lesson for me to lean into the struggle and talk about it. Last time, I talked

A problem was that traversal in a layer would be backward. I'd need to traverse left-to-right to match the build process when building the Prolly Tree from scratch. No problem, I'll just loop through the children backward when processing top-down.

I've been stuck on the incremental insertion of a key in a Prolly Tree, and feeling like I'm in a bog. The version where a Prolly Tree is built from scratch was relatively straightforward. I was able to write it in a day. The incremental version has undergone four or

Last week, I built Prolly Trees from scratch and probed some of its properties. This week, I started building a Prolly Tree incrementally, by inserting one key at a time. It was more challenging than I suspected at first glance, seeing as I implemented it three times. In a typical

Alright, party people. This week I went back to reimplementing Prolly Trees. I wanted to finish out the Lattice Merkle Tree. But given that my goals aren't to just fiddle around in applied research and Prolly Trees already work, I reimplemented Prolly Trees from scratch. I was delighted that the

In Lab note #029 [https://interjectedfuture.com/lab-notes/lab-notes-029-balancing-nodes-in-a-unicit-tree/] , I was thinking about a different way to construct a unicit tree. Can we create both a description of the splits in a tree and a comparator that would make it a partially ordered set? And with that partially ordered set

In my previous lab note #028 [https://interjectedfuture.com/lab-notes/lab-note-028-consistent-splitting-for-node-sizes/] , I was worried that Prolly trees [https://github.com/attic-labs/noms/blob/master/doc/intro.md#prolly-trees-probabilistic-b-trees] were not unicit. When I inserted keys in different orders, there was a small chance that splits would propagate to the end

Last time [https://interjectedfuture.com/lab-notes/lab-note-028-consistent-splitting-for-node-sizes/] , I found balancing nodes seemed to be in conflict with the property of a unicit tree. A balanced tree is desirable for efficient queries. A unicit tree is desirable for Merkle Trees for fast equality comparisons. Was there a way to get both?

👉See Lab note #30 [https://interjectedfuture.com/lab-notes-030-prolly-trees-are-unicit] for corrections. Prolly Trees are unicit, and don't exhibit the bad behavior I've outlines below.Last week [https://interjectedfuture.com/lab-notes/lab-note-027-breadcrumb-to-prolly-trees/] , I was looking at Prolly Trees [https://github.com/attic-labs/noms/blob/master/doc/intro.md#prolly-trees-probabilistic-b-trees] . A major concern

When I found the splitting of nodes for Merkle Search Trees to be problematic [https://interjectedfuture.com/lab-notes/lab-notes-025-split-condition-for-merkle-search-trees/] , I stumbled upon Prolly Trees [https://github.com/attic-labs/noms/blob/master/doc/intro.md#prolly-trees-probabilistic-b-trees] . They were first described by the Noms, a git for databases [https://github.com/attic-labs/

Most desktop, mobile, and web apps use a form-based metaphor to manipulate the state of the digital objects sitting in the database. This is a little odd when you think about it. Most things in the real-world don't work like this, aside from our complex machines. What would it look

I started outlining how to compose different CRDTs together to make an Immutable Conflict-free Resolution Relations [1] construction, based on the Merkle Search Tree. When designing it, I first tried sketching out the entire construction by drawing, but I was left confused. I wasn't sure if all the pieces actually

A major implication not often included in discussions of local-first software is how to deal with migrations. The degree of the problem depends largely on how you fence the boundaries of your system. If your local-first system allows any number of replicas to come in and out of the network