Closed cookieisaac closed 7 years ago
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.
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".
Hey, why was the single pass strategy used instead of the other popular one?
Because the closest book I had on how to do BTrees used it ;)
And it's my favorite :D
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?
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.
Okay, thanks... may I know which book you read?
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
Description
Deletion process produces unexpected result based on current implementation.
Steps to reproduce the issue: 1 Prepare the following test case in
btree_test.go
2 Add a
tree.Print
method for debugging purpose inbtree.go
3 Run the test suite
Describe the results you received:
Describe the results you expected:
See my comment inline in the above section.
To double check the behavior, try to run a visualized b-tree insertion from this website. 1 Selecting max degree as 6 2 Manually insert 0 to 20 (inclusively). [Same underlying tree as above] 3 Manually delete 0 [Correct: Underflow causes redistribution] 4 Delete 1 [Correct: No redistribution. Whereas in the issue reported, the tree is redistributed]
Additional information you deem important (e.g. issue happens only occasionally):
Output of
go version
:go version go1.6.2 linux/amd64
Additional environment details (AWS, VirtualBox, physical, etc.):