0 Replies - 720 Views - Last Post: 09 April 2018 - 10:26 AM

#1 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 7135
  • View blog
  • Posts: 24,238
  • Joined: 05-May 12

Deleting from a B+ Tree -- without the handwaving

Posted 09 April 2018 - 10:26 AM

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.

Is This A Good Question/Topic? 2
  • +

Page 1 of 1