B+Tree Search

Implement search in a B+Tree.

Types

type Node struct {
    Leaf     bool
    Keys     []int
    Values   []int   // only for leaves, same length as Keys
    Children []*Node // only for internal, length = len(Keys)+1
}

func BTreeGet(root *Node, key int) (int, bool)

Rules

• Keys in each node are sorted ascending.
• Internal node routing: choose the first child where key < Keys[i], otherwise the rightmost child.
• Leaves contain the actual values.
• If key is not found, return ok=false.

Notes

• Assume the tree is valid.