Definition

Figure: B-Tree of height 3 containing minimum number of keys

• Every node $x$ has $x.n$ keys and $x.n+1$ children (possibly undefined).
• The key $x.k_i$ separates the range of keys stores in children subtrees, say $l_i$ then $l_1\le x.k_1\le l_2\le x.k_2\le \ldots x.k_n \le l_{n+1}$
• All leaves have same depth
• Each node except root has $t-1$ keys to $2t-1$ keys. Therefore $t$ to $2t$ children.
• Height of tree $h=O(\log_tn)$

Operations

Search $O(th)=O(t\log_tn)$

• Find the subtree where given key exists using linear search
• recurse in that tree

Create $O(1)$

• Create a empty root node
• Insert keys

Insert $O(th)=O(t\log_tn)$

• Find the the leaf node by searching.
• If node is full split on median key to make two children nodes and insert the meadian key into parent node.

For single pass, split whenever you come across a full node while searching so as to be assured to no more split any nodes while shifting the median key upwards.

Splitting

Figure: Splitting a node with $t=4$

• Make two nodes with keys less than and more than the median key respectively.
• Move the children between the keys to respective trees.
• Move the median key to parent node.
• Move the children around the median key to the left and right new nodes respectively.

Delete $O(th)=O(t\log_tn)$

• If key $k$ is in leaf node $x$ then delete $k$ from $x$.
• If key $k$ is in internal node $x$ then
  • If left child $y$ of $k$ has $\ge t$ keys then find predecessor $k’$ of $k$ in $y$. Delete $k’$ from $y$ and replace $k$ by $k’$ in $x$.
  • Otherwise check for right child $z$ and do symmetrically.
  • Otherwise merge $y$ and $z$ along with $k$ into $y$. Recursively delete $k$ from $y$.