B-Trees & B+ Trees: Multi-Way Indexing & Block Size Numericals

A B-Tree of order m is a balanced multi-way search tree designed for disk storage systems where seek latency dominates CPU operations:

1. Every node has at most m children and at most m - 1 keys.

2. Every internal node (except root) has at least lceil m/2 rceil children and at least lceil m/2 rceil - 1 keys.

3. The root has at least 2 children (unless it is a leaf).

4. All leaves appear at the exact same depth (perfect height balance).

B+ Tree Architectural Superiority:

- In a B-Tree, internal nodes hold data pointers, reducing fanout.

- In a B+ Tree, internal nodes store keys and block pointers only. This maximizes fanout, resulting in extremely shallow trees (height 3 to 4 for hundreds of millions of records).

- All leaves are linked sequentially, allowing range queries (WHERE age BETWEEN 20 AND 30) to execute via linear scan without tree re-traversals.

In database systems, each tree node is sized to fit exactly within a single physical disk block of size B bytes.

Let:

- B: Disk block size (bytes)

- K: Search key size (bytes)

- P: Disk block pointer size (bytes)

- P_r: Record pointer size (bytes)

1. Internal Node Order p:

An internal node of order p stores p block pointers and p - 1 keys:

p P + (p - 1) K <= B

p * (P + K) - K <= B implies p <= lfloor frac{B + K}{P + K} rfloor.

2. Leaf Node Capacity q:

A leaf node stores q pairs of (Key + Record Pointer) plus 1 block pointer to the next leaf sibling:

q * (K + P_r) + P <= B implies q <= lfloor frac{B - P}{K + P_r} rfloor.