B-tree and B+ tree — motivation (disk storage), properties

WHY do B-trees exist? (motivation: disk storage)

Intuition Why a binary BST fails on disk

A balanced BST of $N$ keys has height $\approx \log_2 N$ . For $N = 10^9$ that is ~30 levels. Each node = one pointer chase. On a spinning hard disk (HDD), each pointer chase ≈ 1 random read ≈ 10 ms (a mechanical seek + rotation). So a single lookup = $30 \times 10\text{ms} = 0.3$ seconds. Catastrophic. (On an SSD there is no mechanical seek, so a random read is ~0.1 ms — about 100× faster than an HDD — but it is still vastly slower than a RAM access (~0.0001 ms) and is still done in whole blocks. So the same "minimise block reads" logic applies; only the constants shrink.)

The bottleneck is NOT comparisons (CPU is fast), it is the NUMBER of block accesses. Minimise block reads, not comparisons.

WHAT the disk gives us for free. Disks (and SSDs) don't read one byte; they read a whole block / page (e.g. 4 KB or 16 KB) in one I/O. Reading 1 key or 200 keys from the same block costs the same one read.

HOW we choose node size. Pick the number of keys per node so that one node = one disk block. The disk block size dictates the tree's branching factor.

The B-tree: definition and properties

Deriving the height bound (from scratch)

Formula Height of a B-tree

WHY: we want to prove the tree is short. HOW: count the minimum possible number of nodes at each level — that gives the maximum possible height for $N$ keys.

The root has $\ge 1$ key → $\ge 2$ children. Every node at depth $\ge 1$ has $\ge t$ children. So the number of nodes per level grows by a factor of $t$ :

depth	min nodes
0	1
1	2
2	$2t$
3	$2t^2$
$h$	$2t^{h-1}$

Each non-root node holds $\ge t-1$ keys. Total keys: $N \ge 1 + (t-1)\sum_{i=1}^{h} 2t^{i-1} = 1 + 2(t-1)\frac{t^h - 1}{t-1} = 2t^h - 1$ Solving for $h$ : $\boxed{h \le \log_t\!\left(\frac{N+1}{2}\right)}$ So height is logarithmic base $t$ — and $t$ is huge → tiny height.

Figure — B-tree and B+ tree — motivation (disk storage), properties

The B+ tree: definition and why it's the database favourite

	B-tree	B+ tree
Data stored in	all nodes	leaves only
Internal node fanout	lower (carries data)	higher (keys only)
Range/sequential scan	awkward (in-order traversal)	fast (linked leaves)
Search may stop	at internal node	always at leaf

Worked examples

Common mistakes (steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine your books are in a giant warehouse and every time you fetch a shelf it takes a long walk. You don't want to walk 30 times. So instead of putting one book on each shelf-card, you put a whole row of book titles on each card. Now one walk tells you about hundreds of books, and you only walk 3–4 times to find any book in a billion. That fat, short directory of cards is a B-tree. The B+ tree is the same, but it keeps all the real books on the bottom shelves only, and ties those bottom shelves together with a rope so you can grab a whole range of books in a row without walking back up.

Flashcards

What is the real bottleneck B-trees optimise — comparisons or disk accesses?

Disk/block accesses (random reads cost ms on HDD, ~0.1 ms on SSD, both ≫ RAM); CPU comparisons are nearly free.

Why does node size equal the disk block size?

One disk read fetches a whole block for the same cost, so pack a full block of keys per node to maximise fanout and minimise reads.

Max and min number of keys in a B-tree node of min degree

t

(non-root)?

Max

2t-1

, min

t-1

A B-tree node with

k

keys has how many children?

k+1

Height bound of a B-tree with

N

keys, min degree

t

h \le \log_t\!\frac{N+1}{2}

Which node is exempt from the minimum-keys rule?

The root (may have as few as 1 key).

Key structural difference: where does data live in a B-tree vs a B+ tree?

B-tree: in all nodes. B+ tree: only in the leaves; internal nodes are routers.

Why are B+ trees preferred for databases?

Higher fanout (internal nodes hold keys only) + linked leaves give fast range/sequential scans.

Why must all B-tree leaves be at the same depth?

B-trees grow by splitting the root upward, never extending one branch, so the tree stays perfectly balanced — guaranteeing

\log_t N

worst case.

In a B+ tree, can a search stop at an internal node on a key match?

No — internal keys are exact separators but hold no record; you must descend to a leaf to read the actual data.

Why does forcing nodes "at least half full" matter?

It keeps branching factor high so height stays

\log_t N

; merges/splits enforce this invariant.

Connections

Binary Search Tree — the $\log_2$ baseline B-trees improve on for disk.
AVL Tree / Red-Black Tree — in-RAM balanced trees (binary, low fanout).
Disk and Memory Hierarchy — block/page reads, seek time motivation.
Database Indexing — B+ trees as the default index structure (InnoDB, PostgreSQL).
File Systems — NTFS, ext4, HFS+ use B-tree variants for directories.
Big-O Notation — counting I/O complexity vs CPU complexity.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, problem yeh hai: jab data itna bada ho ki RAM me nahi aata aur disk pe rehta hai, toh har ek pointer chase ek slow disk read ban jaata hai. Spinning hard disk (HDD) pe yeh ~10 ms lagta hai (mechanical seek + rotation); SSD pe mechanical seek nahi hota toh ~0.1 ms — par phir bhi RAM se bahut slow, aur dono whole block me padhte hain. Agar normal balanced BST use karo toh height $\log_2 N$ hoti hai, 1 billion keys ke liye ~30 levels — matlab 30 block reads, bahut slow. Asli bottleneck CPU comparisons nahi, block accesses hain.

Trick yeh hai: disk kabhi 1 byte nahi padhti, woh ek poora block (4–16 KB) ek hi read me deti hai. Toh us block ko keys se thoonso — ek node me sau-sau keys. Isse har node ke bahut saare children ban jaate hain (high fanout), aur tree chhota aur mota ho jaata hai — height $\log_t N$ , sirf 3–4 levels. Yahi B-tree hai. Rule simple: minimum degree $t$ , har non-root node me $t-1$ se $2t-1$ keys, sab leaves same level pe (perfectly balanced), aur node split top se hota hai isiliye tree upar se badhta hai.

B+ tree ek upgrade hai jo databases (MySQL, etc.) use karte hain. Isme saara data sirf leaves me rehta hai; internal nodes me sirf router keys hoti hain — yeh keys hamesha exact separators hoti hain (stale nahi), bas record leaf me hota hai. Isse internal node me aur zyada keys aati hain, fanout aur badhta hai, tree aur chhota. Aur leaves ek linked list se jude hote hain, toh "age 20 se 40 ke beech" jaisi range query me ek baar niche jao aur seedha leaves pe chalte raho — baar baar root tak wapas nahi jaana padta. Yaad rakho: "Short & Fat, Half-full, Leaves Level", aur "+" ka matlab leaves pe linked list plus data sirf leaves me.

B-tree and B+ tree — motivation (disk storage), properties

WHY do B-trees exist? (motivation: disk storage)

The B-tree: definition and properties

Deriving the height bound (from scratch)

The B+ tree: definition and why it's the database favourite

Worked examples

Common mistakes (steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Trees

Connections