[Skydiver]

I'll admit it, in my previous B+tree implementation, I didn't really understand how to implement deletion the right way. I just followed the old common wisdom which was to leave nodes under populated and relied on a explicit "compact database" operation to rebuild the tree via bulk-loading. I recall going through my 3 different college data structures and algorithms books trying to grok the deletion algorithms which were always described in high level terms but had no pseudo code or were actually exercises.

Anyway, I've stumbled across the following paper: Implementing Deletion in B+-Trees

It has an elegant recursive solution with pseudo code and flowcharts. May it aid others who need to implement B+ tree deletion.

... Or you could just use the Berkeley DB code without having to understand any of the B+ tree code at all. />

I forgot to add: Not only was I glad to stumble across that, I was also glad to know that it wasn't just me that felt like there was a lot of handwaving going on with regards to how to delete from a B+ tree.