B+Tree Search

Implement equality search in a B+Tree.

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

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

Rules

• Keys inside every node are sorted ascending.
• Internal nodes store separator keys, not values.
• Leaves store the actual values.
• If root == nil, return (0, false).
• If the key is missing, return (0, false).

Internal routing rule

Choose the first child where:

key < Keys[i]

If no such separator exists, choose the rightmost child.

Equivalently:

idx = first index where Keys[idx] > key
child = Children[idx]

This means equality routes right.

For internal keys [10, 20]:

key 5  -> child 0
key 10 -> child 1
key 19 -> child 1
key 20 -> child 2
key 30 -> child 2

Leaf search rule

Inside a leaf, find the key itself and return the matching value.

A clean approach is:

idx = first index where Keys[idx] >= key
if idx exists and Keys[idx] == key: found
otherwise: missing

Professional edge cases

Your solution should handle:

• empty tree,
• root that is already a leaf,
• search key equal to an internal separator,
• search key smaller than all separators,
• search key larger than all separators,
• multi-level internal trees.