A tree index answers "equals," "greater than," and "between" with one structure
Where hashing forces a choice between exact-match speed and range support, a tree index gives up a little raw speed on exact match to support every kind of query at once — this lesson traces that idea from a static first attempt to the dynamic B+ tree every real database actually uses.
After this lesson
You should be able to
- Explain why ISAM's static structure degrades as a table grows through inserts.
- Describe how a B+ tree fixes ISAM's problem, and how its leaf-level linking supports range queries.
The intuition: binary search, but the tree lives on disk
A tree index is a search tree, directly recognizable from CS205ES's binary search tree, except every node here corresponds to a disk block rather than a single value in memory, and each node typically holds many keys instead of just one, since a block can hold far more than a single value. Searching a tree index means reading one block per level, following key ranges down to the block that must contain the answer — the same descend-and-narrow logic as a BST search, now paced by disk blocks instead of memory pointers.
ISAM: a first attempt that works, until the table grows
Indexed Sequential Access Method (ISAM) builds a static tree of index blocks once, pointing down to the actual data blocks below. It is simple and fast to search — but the structure is fixed at creation time, and does not reorganize itself as rows are inserted.
When a new row does not fit in its designated block, ISAM chains an overflow block onto it rather than restructuring the tree — after enough inserts, long overflow chains form, and searches that hit them degrade back toward the linear scan this entire unit exists to avoid. ISAM works well for a table that is built once and rarely changed, but fails exactly the workload most real tables actually see: continuous inserts over time.
B+ trees: self-balancing, and leaves linked for range scans
A B+ tree fixes ISAM's core flaw by rebalancing itself as rows are inserted and deleted, the same self-balancing discipline as an AVL tree from CS205ES, just applied to disk blocks holding many keys instead of memory nodes holding one. Every path from the root to a leaf stays the same length, so search time stays predictable no matter how much the table has grown — no overflow chains, ever.
The other defining feature: all actual data pointers live only at the leaf level, and every leaf block is linked to the next one in sorted order, forming a sorted chain across the bottom of the tree. This is exactly what makes a B+ tree handle both problems this unit raised: descend from the root for exact-match lookup (fast, like a BST search), or descend once to find the start of a range and then simply walk the linked leaves forward (fast, unlike hashing) — one structure, both query shapes.
Root: [30 | 60]
/ | \
[10|20] [30|40|50] [60|70|80]
| | |
(leaves, linked left to right, each pointing to actual rows)
10→20 → 30→40→50 → 60→70→80Try it yourself
A table using ISAM indexing has had thousands of rows inserted since it was built, and searches have become noticeably slower. Diagnose the likely cause, and explain why switching to a B+ tree would fix it.
Need a hint?
ISAM does not restructure itself on insert — repeated overflow chaining is the specific mechanism that degrades its search performance over time.
Check the worked solution
The likely cause is long overflow chains: since ISAM's tree structure is fixed at creation, thousands of inserts that do not fit their designated blocks have been chained as overflow, and searches hitting those chains degrade toward a linear scan. A B+ tree fixes this because it actively rebalances on every insert, so it never accumulates overflow chains and search time stays predictable regardless of how many rows have been added.
Quick check
Why can a B+ tree efficiently answer both an exact-match query and a range query, while a hash index can only handle the first well?
Why this lesson exists
Syllabus mapping
Tree base Indexing, Intuitions for tree Indexes, Indexed Sequential Access Methods (ISAM), B+ Trees: A Dynamic Index Structure
Maps to course outcome CO4.