B+Tree Insert

Implement insertion into a B+Tree with node splitting.

Types

type Node struct {
    Leaf     bool
    Keys     []int
    Values   []int   // for leaves
    Children []*Node // for internal nodes
    Next     *Node   // leaf link
}

type BTree struct {
    Root  *Node
    Order int // max keys per node (>= 3)
}

func NewBTree(order int) *BTree
func (t *BTree) Insert(key int, value int)
func (t *BTree) Get(key int) (int, bool)

Rules

• Keys are unique; inserting an existing key replaces its value.
• Leaf split:
  • Split into two leaves with roughly half the keys.
  • Promote the first key of the right leaf.
  • Update leaf Next pointers.
• Internal split:
  • Promote the middle key.
  • Left keeps keys < promoted, right keeps keys > promoted.

Notes

• The tree starts empty.
• Order in tests is 3 (max 3 keys per node).