Indexing & B+ Trees
An index is an auxiliary structure that speeds up lookups at the cost of extra storage and slower writes.
Cheat sheet
- ▸Clustered index: determines physical row order; one per table.
- ▸Non-clustered: separate structure with pointers to rows; many allowed.
- ▸B+ tree: balanced, all data in leaves, leaves linked → great for range queries.
- ▸Hash index: O(1) equality lookup, no range support.
- ▸Composite index follows leftmost-prefix rule.
- ▸Too many indexes slow INSERT/UPDATE/DELETE.
B-Tree vs B+ Tree
| Aspect | B-Tree | B+ Tree |
|---|---|---|
| Data in | All nodes | Leaves only |
| Leaf links | No | Yes (linked list) |
| Range scans | Slower | Fast |
| Fan-out | Lower | Higher (shallower) |
Visual
[30 | 60]
/ | \
[10 20] → [30 40 50] → [60 70] (linked leaves)Top 10 campus interview questions
Quick quiz
1. How many clustered indexes per table?
2. Best structure for range queries:
3. Index (a,b). Which query can use it?
4. Indexes slow down:
5. LIKE '%abc' typically: