The tree your phone's file system probably uses
A B* tree packs nodes fuller before splitting. A B+ tree moves all data into the leaves and links them in a chain — turning 'find one thing' and 'read everything in a range' into two cheap, different operations.
After this lesson
You should be able to
- Explain the fill-factor improvement a B* tree makes over a plain B-tree.
- Explain why a B+ tree stores all data in its leaves.
- Explain what the leaf-level linked list buys a B+ tree.
B* trees: don't split, redistribute first
Lesson 2's B-tree splits a node the moment it overflows, which can leave both resulting nodes only about half full. A B* tree tries something first: if a neighboring sibling has spare room, shift some keys sideways into it instead of splitting at all. Only when siblings are also full does a B* tree split — and when it does, it splits two full nodes into three, keeping each about two-thirds full instead of one-half.
Fuller nodes mean fewer nodes for the same data, which means Lesson 1's disk-read count drops further still — the same economics, pushed one step harder.
B+ trees: separate the map from the data
In Lesson 2's plain B-tree, a key found partway down the tree already carries its data — search can stop early. A B+ tree deliberately gives that up: internal nodes hold only keys, used purely to route a search downward, and every actual record lives in a leaf, with internal keys often duplicated at the leaf level too.
That sounds like a loss — search always walks all the way to a leaf now, never stopping early. What it buys back is the next section.
Linked leaves: pagination for the whole tree
Every leaf in a B+ tree also holds a pointer to the next leaf in sorted order — the exact linked-list idea from Unit I, applied at the bottom of a tree. Once you have found the first record in a range, you can walk straight across the leaves to collect the rest, never climbing back up to the root.
This is exactly the pagination you already know from an app's infinite-scroll feed: fetch a page, follow a 'next' link to the following page, without ever recomputing where you are from scratch. That is precisely why B+ trees, not plain B-trees, back most real database indexes — databases need both 'find this one row' and 'give me this whole range,' and only the B+ tree makes both cheap at once.
Internal nodes (keys only, routing):
[30 | 60]
/ | \
Leaf level (data, linked left-to-right):
[10 20] -> [30 40 50] -> [60 70 80] -> NULLTry it yourself
Explain, in your own words, why a database index that must support 'find student 12345' and 'list all students between roll 12000 and 12999' would choose a B+ tree over a plain B-tree.
Need a hint?
Consider what a plain B-tree would have to do to answer the range query, one record at a time.
Check the worked solution
A plain B-tree answers the single lookup fine, but a range query would mean re-searching from the root for every single roll number in the range, or a fragile manual in-order walk through internal nodes. A B+ tree answers the single lookup with one root-to-leaf search — no faster than the plain tree — but answers the range query with one search plus a leaf-to-leaf walk, which is why real systems accept the plain tree's small loss (no early stopping) for the range-query win.
Quick check
Why does a B+ tree store actual records only in its leaves, never in internal nodes?
Why this lesson exists
Syllabus mapping
B* Tree · B+ Trees
Maps to course outcomes CO1, CO2, CO4.