Incorrect deletion result from current B-Tree implementation about btree HOT 9 CLOSED

Because the closest book I had on how to do BTrees used it ;)

from btree.

And it's my favorite :D

from btree.

I believe I got most of my stuff from https://en.wikipedia.org/wiki/Introduction_to_Algorithms

I'd also check out http://assets.en.oreilly.com/1/event/36/How%20TokuDB%20Fractal%20Tree%20Databases%20Work%20Presentation.pdf and https://en.wikipedia.org/wiki/Fractal_tree_index

from btree.

I believe this is actually working as intended.

In this BTree implementation, the tree makes a single pass down the tree to find/remove the node. All redistribution is done on the way down, none on the way up. Also, while traversing the tree, we only have a view of the current node and its direct children. Given that constraint, at each node we traverse we must assume the worst case about our children's children (that they have the least number of nodes they could possibly have) and act accordingly.

While in your case, the leaf node did have enough elements, the root node doesn't know that (it only sees itself and its children, not its children's children. Consider this case:

NODE:[11]
  NODE:[5 8]
    NODE:[1 2]
    NODE:[6 7]
    NODE:[9 10]
  NODE:[14 17]
    NODE:[12 13]
    NODE:[15 16]
    NODE:[18 19 20]

The root here says "my child has 2, and its child may have none to spare". So, it performs a merge before traversing down. By merging first, it knows that, should the child not have enough, its parent will have a spare value to give.

In short, we use option 2 of https://en.wikipedia.org/wiki/B-tree#Deletion: "Do a single pass down the tree, but before entering (visiting) a node, restructure the tree so that once the key to be deleted is encountered, it can be deleted without triggering the need for any further restructuring"

I believe that, had we implemented option 1 ("Locate and delete the item, then restructure the tree to retain its invariants"), the tree would behave as you expect and would not have rebalanced after the deletion of 1.

from btree.

Thanks for clarifying the assumptions. This implementation, by design, takes a proactive tree restructure approach during deletion to save one extra pass, instead of the reactive approach which aims to reduce unnecessary restructure operations. Agree to close the issue as "Working as Designed".

from btree.

Hey, why was the single pass strategy used instead of the other popular one?

from btree.

The Btree I implemented in C++ is designed to be used as a "disk btree" to be used at scale in my data management system... which implementation would you recommend that I use?

from btree.

I think single-pass is better for disk, but you could also look at fractal trees and the like that are even better for disk purposes.

from btree.

Okay, thanks... may I know which book you read?

from btree.