Lab note #034 Incremental insertion into Prolly Trees
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 B+tree, we'd traverse down a path from the root to a leaf. We'd change that leaf and cascade changes up the same path in the tree. In a Prolly Tree, it's slightly different. All the sibling nodes to the right of the changed leaf node have the possibility of being changed. That means instead of a seam, it's a swath of nodes that could be changed. The width of this swath could be just two or three nodes wide but has a small chance of being the entire right side of the tree.
To implement this, we have to do a depth-first traversal down to the target leaf node. Then from the target leaf node, we have to do a breadth-first traversal from the bottom up. I think it's the combination of the two that makes this tricky. Once the target leaf is found, we start traversing to the right to check for boundary nodes. Once we find one, we check if this boundary is the same as our previous tree. If not, we keep going. If it is, we can skip processing the rest of the sibling nodes to the right in this layer because they will not change. Then we can recurse back up and repeat all the way until the root.
After getting it to work, I wondered if my life would have been made easier simply by linking all nodes on the same layer in a linked list. From my experience with Rust, you generally don't want to have multiple links to a node. Eventually, I'm going to reimplement this in Zig, and I'm not sure how multiple links would work with allocators, so I'm simply playing it safe. For now, I've already dealt with the headache so I might as well just take it the rest of the way.
In other news, I got into the Recurse Center, a programmer's retreat, where I'll be focusing on this work with other peers. I look forward to having other people to share this work with, to get feedback from, and to see how a remote work environment works nowadays. I'm pretty excited about that.
In addition, I'll be attending Gena Gorlin and Dan Shipper's Max Your Mind course, where we'll learn how to use ChatGPT as a daily AI coach to journal, make decisions, and identify psychological blockers. There are definitely things in my life that I procrastinate on and mental blockers that get in the way of achieving the goals I want done. For me, the value of the course is the psychological aspect of coaching that I'd want to get right. Unlike programming, I know little about it and figured getting it done right is more efficient than stumbling around on my own.
Can't wait for the Prolly Tree to be done. I will be excited when it does.