google/btree

Incorrect deletion result from current B-Tree implementation

cookieisaac opened this issue · 9 comments

cookieisaac commented

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

package btree

import (
    "flag"
    "fmt"
    "testing"
    "os"
)

var btreeDegree = flag.Int("degree", 3, "B-Tree degree")

func TestForBTreeDeletion(t *testing.T) {
    tree := New(*btreeDegree)
    fmt.Println(tree)

    for i := 0; i < 21; i++ {
        if x := tree.ReplaceOrInsert(Int(i)); x != nil {
            t.Fatal("insert found item", i)
        }
    }
    fmt.Println("Before deletion")
    tree.Print(os.Stdout)

    for i := 0; i < 3; i++ {
        if x := tree.Delete(Int(i)); x == nil {
            t.Fatal("insert didn't find item", i)
        }
        fmt.Println("After deleting ", i)
        tree.Print(os.Stdout)
    }

}

2 Add a tree.Print method for debugging purpose in btree.go

// Print is for debugging purpose on CLI
func (t *BTree) Print(w io.Writer) {
    t.root.print(w, 0)
}

3 Run the test suite

go test -v

Describe the results you received:

Before deletion  *[<===== This is the original tree with degree of 3 after inserting 0 to 20]*
NODE:[8]
  NODE:[2 5]
    NODE:[0 1]
    NODE:[3 4]
    NODE:[6 7]
  NODE:[11 14 17]
    NODE:[9 10]
    NODE:[12 13]
    NODE:[15 16]
    NODE:[18 19 20]

After deleting  0 *[<====== After deleting 0, `NODE[0 1]` underflows and causes redistribution ]*
NODE:[11]
  NODE:[5 8]
    NODE:[1 2 3 4]     **[<====== This NODE has enough items so that deleting 1 shouldn't cause an underflow]**
    NODE:[6 7]
    NODE:[9 10]
  NODE:[14 17]
    NODE:[12 13]
    NODE:[15 16]
    NODE:[18 19 20]

After deleting  1  [<===== WRONG: The underlying B-tree is redistributed]
NODE:[5 8 11 14 17]
  NODE:[2 3 4]
  NODE:[6 7]
  NODE:[9 10]
  NODE:[12 13]
  NODE:[15 16]
  NODE:[18 19 20]

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

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.):

gconnell commented

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.

cookieisaac commented

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".

CheyenneForbes commented

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

gconnell commented

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

  • 👍1
gconnell commented

And it's my favorite :D

  • 👍1
CheyenneForbes commented

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?

gconnell commented

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.

CheyenneForbes commented

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