Properties
- All leaves at same depth
- Node has between ⌈M/2⌉ and M-1 keys (root exception)
- Keys in each node are sorted
Advertisement
Insert with split
Insert into leaf. If node overflows (M keys), split: middle key promotes to parent, node splits in two. Recurse up.
Advertisement
Delete with merge/redistribute
Remove key. If node underflows, redistribute with sibling or merge two nodes into one. Recurse up.