The AVL tree from the previous lesson is unbeatable... as long as the tree fits in RAM. But imagine TaskFlow deployed at a company with ten million tasks: the index no longer fits in memory and lives on disk, and disk changes the rules of the game — you don't read byte by byte but in blocks of thousands of bytes, and each read costs tens of thousands of times more than a RAM access. Suddenly, the metric that matters isn't "how many comparisons do I make" but "how many blocks do I read", and the binary tree, with one measly node per hop, reads an almost entire block just to use a few bytes. The B-tree inverts the design: huge nodes, sized exactly to a block, with hundreds of keys and children each — extremely short, extremely wide trees where three or four reads are enough to find a key among millions. In this lesson you'll understand why it exists, how its insertion works with node splitting (with diagrams, not a complete implementation), what its B+ variant adds, and where you run into it every day: in the index of any database.

1. Disk changes the rules: blocks and access cost
2. What a B-tree is: order, properties, and invariants
3. Searching a B-tree
4. Inserting: growing by splitting nodes
5. The B+ tree: data in the leaves, leaves chained together
6. Where they live: databases and file systems — TaskFlow on SQLite
7. BST vs AVL vs B: the comparison table

In module 1 we saw the memory hierarchy in passing; now the bill arrives. Orders of magnitude (rounded, but faithful):

And the key nuance: disk doesn't sell individual bytes. It reads in blocks (or pages, typically 4-16 KB): asking for 8 bytes costs the same as asking for the whole 4,096-byte block. Two immediate consequences:

• The cost of an on-disk algorithm is measured in number of blocks read, not in comparisons. Comparisons within a block already loaded into RAM are free by comparison.
• A good disk algorithm must use the whole block every time it pays for one.

Now look at the AVL through these glasses. Ten million keys → height ≈ 23. Each node-to-node hop is, in the worst case, a different block (the nodes, created at different times, live scattered): 23 block reads to fetch... 23 tiny nodes of a few dozen bytes each. Of every 4 KB block paid for, we use maybe 1%. On a mechanical disk, 23 reads is a quarter of a second — for one search. The binary tree is a magnificent design for RAM and a waste for disk.

The idea that fixes it is crushingly logical: if the block arrives whole anyway, fill it with keys. A 4 KB node can house hundreds of keys and child pointers; with hundreds of children per node, the height collapses.

A B-tree of order m is a search tree where each node can have up to m children. Its properties:

• Each node stores up to m − 1 sorted keys; an internal node with k keys has exactly k + 1 children.
• A node's keys act as separators: child i contains only keys between the parent's key i−1 and key i — the direct generalization of "left smaller, right larger" to many children.
• Every node (except the root) is at least half full: at minimum ⌈m/2⌉ − 1 keys. No scrawny nodes wasting blocks.
• All leaves are at the same level: the B-tree is perfectly balanced, always. No balance factors, no rotations: its growth mechanism (we'll see it shortly) makes imbalance impossible.

A B-tree of order 4 (a toy-sized pedagogical "root"): the root has 2 keys and 3 children; the middle child contains only keys between 20 and 40. In real practice, with 4-16 KB blocks, the order m runs into the hundreds: and there lies the height miracle —

The height grows like log_m(n), and with m = 200, log₂₀₀(10⁷) ≈ 3. Three block reads to find one task among ten million (and in practice fewer: the root and the second level stay cached in RAM). Against the AVL's 23, it's the difference between a usable index and a dragging one.

Search generalizes the BST descent: at each node, instead of one comparison and two paths, you find the key's position among the separators (inside the node you can use binary search — module 1 working inside every block!) and descend through the child in the corresponding gap. Searching for 31 in the diagram's tree:

1. Root [20 | 40]: 31 is between 20 and 40 → middle child. (1 block read)
2. Node [25 | 31 | 38]: 31 is here. Found. (2 blocks read)

In pseudocode (this lesson works with pseudocode and diagrams; the complete implementation of a B-tree — with its block management, occupancy minimums, and merges on deletion — is a weeks-long project beyond the course's level, and in practice it's written by database engines, not applications):

Cost: O(log_m n) block reads, with O(log₂ m) free comparisons inside each one.

Here lies the B-tree's elegance. Insertions always go into a leaf (descending as in the search), and the key settles in order inside it. What if the leaf is already full (has m − 1 keys)? Then it splits:

1. The overflowing leaf splits into two nodes, each with half the keys.
2. The median key stays in neither: it moves up to the parent as the new separator between the two half-nodes.
3. If that overflows the parent, the parent splits the same way... and the split can propagate upward. If the root overflows, it splits and a new root is created with a single key: it's the only moment the tree gains height.

Let's watch it step by step, inserting 10, 20, 30, 40, 50 into an empty B-tree of order 4 (maximum 3 keys per node):

Steps 1-3 — 10, 20, 30 fit in the root-leaf:

Step 4 — 40 arrives: the leaf would have 4 keys. Split: it splits into [10] and [30|40], and the median 20 moves up... but there's no parent: a new root is created.

Step 5 — 50 goes down to the right and fits: [30|40|50].

Step 6 — let's insert 60: the right leaf overflows, splits into [30] and [50|60], and the median 40 moves up to the root, which has room:

Pause on the detail that explains everything: the B-tree doesn't grow downward, it grows upward — the leaves stay where they are, and it's the root that, once in a great while, rises a floor. That's why all leaves are always at the same level: they were born at the same level and only spread out horizontally. Perfect balance isn't maintained with corrective rotations as in the AVL: it's structurally impossible to unbalance it. (Deletion is the reverse process — nodes falling below the minimum merge with siblings or borrow keys from them — with the same guarantee.)

In pseudocode:

A split costs O(m) (distributing keys between two blocks), and there's at most one per level: insertion in O(log_m n) block writes. And the 50% minimum occupancy is guaranteed by construction: each half of a split is born exactly half full.

The variant that dominates the real world is the B+ tree, with two tweaks on the B-tree:

• Internal nodes store only separators (guide keys, with no associated data); the complete data lives exclusively in the leaves. Advantage: with no data to carry, each internal block fits more separators → higher effective order → an even shorter tree. (A curious consequence: separator keys can appear duplicated — once as a guide above and once with their data in the leaf.)
• The leaves are chained together in a sorted linked list (module 2 reappearing in the engine room of databases!).

That chaining is gold for this module's star query: the range. In the BST/AVL, range_query(a, b) navigated the tree with pruning; in the B+, you descend just once to a's leaf and then advance in a straight line along the chain of leaves until passing b — sequential reads of contiguous blocks, the cheapest access pattern that exists on disk. "Tasks with id between 1,000 and 5,000": one descent plus a stroll. For the same reason, a full in-order traversal doesn't even touch the internal nodes.

B/B+ trees are, almost certainly, the data structure you used most often today without knowing it:

• Databases: the indexes of SQLite, PostgreSQL, MySQL (InnoDB), Oracle, and SQL Server are B+ trees (or very close variants). Every CREATE INDEX plants one.
• File systems: NTFS (Windows), APFS (Apple), Btrfs, and ext4 (Linux) use B-trees for directories and metadata — 06-01's folder hierarchy, indexed.

Let's close the circle with TaskFlow. The day its tasks move from our in-RAM structures to a database:

Read the second statement with this module's eyes: (priority, id) is exactly the composite key we invented in 06-04 for the urgency index — the database and you have arrived at the same solution, because it's the same question. And the final SELECT executes as we just described: descent to the first (1, ...), stroll along the chained leaves until passing (3, ∞), results already sorted without sorting anything. All of module 6, served in three lines of SQL — the difference is that now you know what is underneath and why it's fast, which is what separates someone who uses a database from someone who understands it.

The module's progression, read straight through: the BST contributed the idea (compare and discard), the AVL added the guarantee (maintained balance), and the B-tree adapts both to the hardware (the unit of cost is the block). Same logic, three habitats.

• Measuring a disk tree in comparisons. The correct metric is block reads; inside a block in RAM, comparing is free for practical purposes. Confusing the metrics leads to irrelevant "optimizations".
• Believing the median stays in one of the split halves. No: it moves up to the parent as a separator. If your diagrams' key counts don't add up, check this — it's the number-one slip when tracing splits by hand.
• Thinking the B-tree needs AVL-style rebalancing. There are no rotations: growing from the top (root split) keeps all leaves at the same level by construction. They're two different philosophies of balance.
• Confusing B with B+. In the classic B-tree, internal nodes also carry data; in the B+, only separators, and the leaves are chained. When you read "databases use B-trees", it almost always means B+.
• Practical tip: next time a SQL query with WHERE ... BETWEEN or ORDER BY runs slow, ask yourself whether a B+ index exists whose leading columns match the query (the order of the columns in the index matters: it's the tuple order of 06-04). EXPLAIN will tell you whether the engine is using it.

In an initially empty B-tree of order 4 (maximum 3 keys per node), insert in this order: 8, 5, 1, 7, 3, 12, 9, 6. Draw the tree after each split, indicating which key moves up. How many splits occur and what is the final height?

An internal B+ tree node must fit in a 4,096-byte block. Each key (task id) takes 8 bytes and each child pointer another 8. (a) What maximum order m does the block allow? (b) With that m, how many tasks at most does a tree of height 2 index (root + 1 internal level + leaves, assuming leaves of up to 255 entries)? (c) What height would a binary tree need for that amount?

For each TaskFlow scenario, choose among dict/HashTable, AVLTree, and B+ tree (via a database), and justify in one sentence using the correct metric: (a) an in-memory cache of active sessions, queried by exact token; (b) an in-RAM index of the sprint's 10,000 tasks by (priority, id), with constant range listings; (c) the complete history of 20 million archived tasks, queried by date ranges.

Solution 1

• 8, 5, 1 fill the root: [1|5|8].
• 7 overflows → split 1: halves [1|5] and [8]... with median 7 rising to a new root. Careful: the four keys in play, sorted, are 1, 5, 7, 8; they split as [1|5], 7 moves up, [8] remains. Tree: root [7], children [1|5] and [8].
• 3 goes down to the left: [1|3|5]. 12 goes down to the right: [8|12]. 9: [8|9|12].
• 6 goes down to the left, which overflows (1, 3, 5, 6) → split 2: [1|3], 5 moves up, [6] remains. Root: [5|7] with children [1|3], [6], [8|9|12].

Total: 2 splits, final height 1 (root + leaves). Comment: notice that the eight keys ended up distributed with all leaves at the same level and none below the minimum (⌈4/2⌉ − 1 = 1 key) — the invariant held on its own, without any external rule intervening.

Solution 2

(a) A node with k keys has k + 1 pointers: 8k + 8(k+1) ≤ 4096 → k ≤ 255. Order m = 256. (b) Root with 256 children → 256 internal nodes → 256 × 256 = 65,536 leaves of up to 255 entries ≈ 16.7 million tasks with height 2 (three block reads, and the first two probably cached). (c) A binary tree would need height ⌊log₂(16.7·10⁶)⌋ = 23. Comment: the moral in one sentence — same logarithm, different base, and the base is dictated by the block size: log₂₅₆ versus log₂ is the difference between 3 reads and 23.

Solution 3

(a) dict/HashTable: exact key, no need for order, all in RAM — unbeatable O(1); a tree would pay a logarithm in exchange for nothing. (b) AVLTree: constant ranges and ordering in RAM with ids arriving in increasing order — the hash knows nothing of ranges and the BST would degenerate; the B+ would be over-engineering with no disk involved. (c) B+ tree (database): 20 million don't fit comfortably in RAM and the query is by range — three block reads and a stroll along chained leaves; an on-disk AVL would make ~24 block hops per descent. Comment: no answer is "the best structure in the abstract"; all three are "the best for that access pattern in that habitat" — the criterion we'll develop in depth in module 8.

The B-tree completes the module's ladder: when data moves to disk, the unit of cost shifts from the comparison to the block, and the answer is a tree tailored to the block — nodes with hundreds of keys, height 3 or 4 for millions of elements, perfect balance maintained by splits that grow the tree at the root, and in its B+ variant, chained leaves that turn ranges into sequential reads. Now you know what a CREATE INDEX plants and why TaskFlow's BETWEEN on SQLite will fly: it's the same (priority, id) index you built by hand, in industrial form. One promise remains to be kept, and it's an old one: in module 4 we used heapq as a black box for the UrgentInbox, swearing that one day we'd open it. That day is the next lesson: the heap, a binary tree that gives up the BST's total order in exchange for one thing only — always having the minimum at hand — and which, thanks to 06-02's array representation, doesn't even need nodes. Let's open the box.