Understanding B‑Tree vs B+‑Tree: Principles, Insertion & Why B+ Beats B for Indexing

B‑Tree Basics

Dynamic search trees include binary search trees, balanced trees, red‑black trees, B‑trees, etc. B‑trees have O(log₂N) time complexity; reducing tree height improves lookup efficiency, especially when data is stored on external disks.

Difference from Red‑Black Trees

B‑tree nodes may have many children, while red‑black trees are binary (max two children). Both have similar height O(log N) for N nodes.

Definition of a B‑Tree

Each node can have up to m children.

Except root and leaves, each node must have at least ⌈m/2⌉ children.

If the root is not a leaf, it must have at least two children.

All leaves are on the same level and contain no key data.

Node Structure (C‑like)

struct BTNode {
    int keyNum;          // actual number of keys
    PBTNode parent;      // pointer to parent node
    PBTNode *ptr;
    keyType *key;        // array of keys
}

B‑Tree Insertion

Insertion Rules

If the key already exists, replace the old value.

If the key does not exist, insert it into the appropriate leaf.

For an m‑order tree of height h, new keys are usually inserted at level h.

If the target node has fewer than m‑1 keys, insert directly.

If the node already has m‑1 keys, split the node at the middle key, create a new node, and push the middle key up to the parent.

Repeated splits may propagate to the root, increasing the tree height by one.

B+‑Tree Insertion

Insertion Steps

1. Empty tree: insert the key as the root.

2. Leaf node: locate the leaf via the key and insert. If the leaf exceeds m‑1 keys, split it into two leaves; the left leaf keeps the first ⌈m/2⌉ records, the right leaf the remaining, and the middle key is promoted to the parent index node.

Promoted keys point to left and right child nodes respectively.

3. Index node: if the node has ≤ m‑1 keys, insertion finishes; otherwise, split the index node similarly and promote the middle key.

Why B+‑Tree Is Preferred for Database and File Indexes

Lower disk I/O cost because internal nodes store only keys, not full records.

Search paths are uniform: every key lookup follows a single root‑to‑leaf path, giving stable query performance.