B-Tree

B-tree

Search-friendly multi-way balanced tree; keeps leaves at same depth.

MINIMUM (m)

Smallest #keys in any non-root node; design parameter of the tree. :contentReference[oaicite:9]{index=9}

MAXIMUM

2 × MINIMUM; largest #keys a node can hold. :contentReference[oaicite:10]{index=10}

Rule 1

Root may have 1 key; other nodes ≥ m keys. :contentReference[oaicite:11]{index=11}

Rule 2

Node ≤ 2 m keys. :contentReference[oaicite:12]{index=12}

Rule 4

Non-leaf with k keys has k + 1 children. :contentReference[oaicite:13]{index=13}

Rule 5 (ordering)

Key i separates child i (

Rule 6

All leaves at the same depth (balanced). :contentReference[oaicite:15]{index=15}

Loose insertion

Temporarily allow node to hold MAX + 1 keys. :contentReference[oaicite:16]{index=16}

Split operation

Divide overflow node into left m, median, right m keys; push median up.

Loose removal

Temporarily allow node to drop to m – 1 keys. :contentReference[oaicite:17]{index=17}

Borrow (deletion)

Move one key from rich sibling through parent to the poor node.

Merge (deletion)

Fuse poor node with sibling and pull down parent separator key.

Search cost

O(log₍m₎ N) because tree height is logarithmic in fan-out.

Overflow

Node with 2 m + 1 keys – triggers split.

Underflow

Node with m – 1 keys – triggers borrow/merge.

In-order predecessor

Largest key in left subtree; used to delete internal key.

Height of B-tree

≤ ⌈log_{m+1}(N)⌉.

Fan-out

Number of children of a node; up to 2 m + 1.

Real-world use

Databases & filesystems (minimizes disk seeks).