Oops, saved the previous entry too early.

Removing from a leaf node: should I merge with an adjacent leaf node? No idea, but I won't do that right now. Right now I only care about index nodes.

So, when going downwards, if an index node has only the minimal number of keys, it should be merged with one of its siblings. The sibling will have at most 2b+1 keys. There are several cases:

  • No adjacent node with same parent: oops, what do I do now? There's not really anything I can do, is there? Can this happen? Yes it can. But I will just not split in that case. But I have to: the node will otherwise end up with fewer than b keys, and that is not acceptable.
  • Adjancent node has at most b+1 keys: combine with that.
  • Adjancent node has more than b+1 keys: total number of keys in the two nodes is at least 2*b+2, so create two nodes with half of the total number of keys in each, they're both going to have at least b+2 nodes.

These rules are not working. If I have a tree like this:

a c
| \__________
v           v
a *         c d
|           | \_______
v           v        v
a aa        c cc     d dd

If I now remove a or aa, I should merge the index node 'a ', and I can't do that. I could join it with the 'c d' index node, and create 'a c' and 'd '. Is that what I'm supposed to do?

Let's see what the btrfs code does, if I can decipher that. I can't, or at least not easily. Let's see if I can find a doc describing B-trees. There might be something on Safari Online.

Hmm, Sedgewick seems to suggest it is OK to let an index node become too small. I'll start with that, and modify my tests accordingly.

Then I can use the rules above.

In order to merge nodes, I will need to do that before recursing into the node.

Bah, forgot this entry open for a day.