|
I invite you to upgrade to a paid subscription. Paid subscribers have told me they have appreciated my thoughts & ideas in the past & would like to see more of them in the future. In addition, paid subscribers form their own community of folks investing in improving software design—theirs, their colleagues, & their profession.
One of my experimental projects is to see if I can write a library-quality, performance-competitive basic data structure with a genie. This started when I was building an experimental database project for an experimental programming language (are you sensing a theme here?) project. If you can’t get the data structures right, none of the rest of those higher layers are going to work either.
This isn’t vibe coding. I care very much about the internal details of these projects because the moment I miss something, the genie does something that hamstrings us later. Well, the genie or I, but I’ll get to that later.
Thanks so much to sponsor Augment Code (their products appear in this post). Congratulations on the GA release of Remote Agents. I was skeptical when I heard of a horde of free genies running around my code, but I’m warming to the idea. There’s subtlety, nuance, & skill to picking tasks for a remote agent but that’s the joy of working on rapidly changing technology—learning those skills & sharing them. Which is what this community is so good at.
B+ Tree
The data structure I’m building is an efficient, scalable map. The goals are:
Fast retrieval—O(log n) where n is the number of keys in the map.
Fast insertion—O(log n)
Fast deletion—O(log n)
Crucially, fast range scanning. We want to be able to iterate from key 1 to key 2 in O(m + log n) where m is the number of keys between key 1 & key 2.
The basic operations are put (sometimes called insert), get, delete, & scan. The data is stored in a tree of nodes.
Leaf nodes map from keys to values.
Internal, or branch, nodes, map from keys to nodes, either branch nodes or leaf nodes.
Nodes have a fixed capacity.
The empty tree is a header object & an empty leaf node:
 |
After we insert data at keys 1, 2, 3, & 4, the leaf is full:
 |
Here’s where the B+ Tree gets tricky. What happens when we insert key 5?
 |
We need to split the leaf into two leaves & introduce a branch node with the leaves as children:
 |
There are several tricky edge cases to get right in insertion & splitting, especially when we have a multi-level tree & leaf splitting triggers branch splitting. And insertion isn’t even the tricky bit. Deletion is a nightmare.
Supporting the fast scan operation requires that the leaf nodes are all at the same (bottom) level of the tree & that they are linked together.
 |
Experiment
This is an experiment in augmented coding not a data structures tutorial so I’ll save the B+ Tree details for another day (it’s so cool though y’all!) I’ve been working on this project off and on for the better part of a month, including starting over twice when things got too complicated for the genie to make further progress. For educational purposes I’m implementing it in Rust, a language I hadn’t touched until I started the project.
The problem I kept running into was runaway complexity. The genie would implement the next feature, but add excess complexity in the process. The next feature took longer & had more stumbles along the way. Eventually the genie just couldn’t make further progress.