Indexes for Database Management Systemss
Indexes are auxiliary data structures that let a database find rows without scanning the whole table. The B+ tree is the standard ordered index, supporting point and range lookups. Hash indexes give fast equality lookups, and other structures such as bitmap or skip-list indexes serve specific workloads. Each index speeds reads but adds cost to writes.
Stage: Storage and Indexes · Part of the Database Management Systems roadmap · Last reviewed 19 November 2026
What to learn in Indexes
- Walk through a B+ tree search, insert and node split by hand
- Explain why B+ trees keep data in leaves linked together
- Choose between a B+ tree and a hash index for a query pattern
- Describe latch crabbing for concurrent access to a tree
- Design a composite index and explain column order
- Explain covering indexes and when an index-only scan is possible
Indexes interview questions
Why do databases use B+ trees instead of binary trees?
A B+ tree node holds many keys and matches the disk page size, so the tree is shallow and a lookup needs few page reads. Linked leaf nodes also make range scans efficient. A binary tree would be tall and cause many random reads.
Does column order matter in a composite index?
Yes. A composite index on (a, b) is sorted by a, then b, so it serves queries filtering on a, or on a and b, but not on b alone. Put columns used in equality filters first and range columns after them.
Where Indexes fits in the Database Management Systems roadmap
Indexes belongs to the Storage and Indexes stage (advanced level). How data lives on disk.
Other units in this stage
Back to the full Database Management Systems roadmap