B trees

Why it exists

Binary search trees have height about $\log_2 n$, too many disk reads for a big index. A B tree is a search tree whose nodes are as large as a disk block and hold many keys, so the tree is very flat: a few block reads find any key, and the tree stays balanced under insertions and deletions without reorganising the whole file. GATE asks for the order of a B tree for a given block size, the minimum and maximum number of keys or nodes for a given height, and the result of insertions and deletions.

Prerequisites

You need ordered indexes (ordered indexes) and binary search trees (binary search trees); a B tree is the multiway generalisation of a BST that stays balanced.

Precise definitions

A B tree of order $m$ (maximum number of children, $m \ge 3$) is a rooted tree such that:

1. every node has at most $m$ children and at most $m - 1$ keys;
2. every node except the root and the leaves has at least $\lceil m/2 \rceil$ children, so every non-root node has at least $\lceil m/2 \rceil - 1$ keys;
3. the root has at least $2$ children unless it is a leaf;
4. a node with $k$ keys $k_1 < \cdots < k_k$ has $k + 1$ children (if it is not a leaf), and all keys in the $i$-th subtree lie between $k_{i-1}$ and $k_i$;
5. all leaves are on the same level.

Each key of an inner node comes with a pointer to the record (or the record itself): in a B tree every key appears exactly once in the tree, in an inner node or in a leaf.

Order from the block size. A node with $p$ tree pointers holds $p - 1$ keys and $p - 1$ record pointers. With block size $B$, tree pointer $P$, key $V$ and record pointer $P_r$: the node must satisfy $p \cdot P + (p - 1)(V + P_r) \le B$, so $p = \Big\lfloor \frac{B + V + P_r}{P + V + P_r} \Big\rfloor.$ Example: $B = 512$, $V = 9$, $P = 6$, $P_r = 7$: $p = \lfloor 528/22 \rfloor = 24$.

How it works

Search

Start at the root. In a node, find the first key $\ge$ the search key by comparing with the keys in order (or binary search inside the node). If it is equal, found. Otherwise follow the child pointer between the two keys around the search key. At a leaf with no match the key is absent. At most $h$ nodes (blocks) are read, where $h$ is the height; a search may stop earlier at an inner node.

Insertion

1. Search for the key; if present, stop (keys are unique).
2. The key goes into the leaf where the search ended (a B tree grows at the leaves).
3. If the node now has $m$ keys (one more than allowed) it overflows: split it around its median key (position $m // 2$, counting from $0$); the median moves up into the parent; the left part stays, the right part forms a new node. The parent may overflow in turn, and so on.
4. If the root splits, a new root with the single median key is created: the tree grows one level taller at the top, so all leaves stay at the same depth.

Inserting $10, 20, 30, 40, 50, 60, 70, 15, 25$ into an empty tree of order $4$ (at most $3$ keys per node): the first three keys fill the root; $40$ overflows it and $30$ goes up into a new root. $70$ makes $[40, 50, 60]$ overflow and $60$ moves up; $25$ overflows $[10, 15, 20]$ and $20$ moves up. The final tree has the root $[20, 30, 60]$ and the leaves $[10, 15]$, $[25]$, $[40, 50]$, $[70]$.

Deletion

1. Find the key. If it is in an inner node, replace it by its predecessor (the largest key of the left subtree; the successor works too) and delete that key from its leaf.
2. Remove the key from the leaf. If the leaf still has at least $\lceil m/2 \rceil - 1$ keys, stop.
3. Otherwise the node underflows. If a sibling has a spare key, borrow through the parent: the separator in the parent moves down into the node and the sibling's nearest key moves up into the parent. If no sibling has a spare key, merge the node with a sibling and the separator between them; the parent loses a key and may underflow in turn.
4. If the root loses its last key, its only child becomes the new root: the tree gets one level lower.

On the tree above (order $4$, minimum $1$ key per non-root node) the deletions $25, 15, 10, 40, 20$ show borrowing from a sibling, replacement of an inner key by its predecessor, and two merges (the parent loses a key each time).

Capacity and height

For a B tree of order $m$ with $h$ levels (the root is level $1$) and $c = \lceil m/2 \rceil$:

• maximum number of keys: every node full: $m^h - 1$;
• minimum number of keys: root with $2$ children (1 key), every other node with $c$ children ($c - 1$ keys): $2c^{h-1} - 1$.

Consequently a tree with $n$ keys has height $h$ with $\lceil \log_m (n + 1) \rceil \ \le\ h\ \le\ \Big\lfloor \log_{c} \tfrac{n + 1}{2} \Big\rfloor + 1.$ The extreme trees (completely full, and the leanest possible) were built node by node for orders $3$ to $7$ and heights up to $4$ and have exactly these numbers of keys; random insertions and deletions never left the bounds. For the order $24$ above: a $3$-level tree holds between $2 \cdot 12^2 - 1 = 287$ and $24^3 - 1 = 13\,823$ keys.

Worked examples

Cheat box

Traps and GATE patterns

Connections

A B tree is the balanced multiway version of the binary search tree (BST); the dynamic alternative that keeps all keys in the leaves is the B+ tree, the usual index of database systems (B+ trees); it replaces static multilevel indexes (ordered indexes).

PYQs

A B-tree of order 4 is built from scratch by 10 successive
insertions. What is the maximum number of node
splitting operations that may take place?

A B-Tree used as an index for a large database table has
four levels including the root node. If a new key is
inserted in this index, then the maximum number of nodes
that could be newly created in the process are:

Self-check

Revision card

References