The whole course, meeting itself at the last lesson
A database index is a B+ tree from Unit III, stored in the file organization from Lesson 5, built to answer the exact question a hash table answers in Unit V — with one added ability neither could give you alone.
After this lesson
You should be able to
- Explain what an index trades away and what it buys in return.
- Explain why a database index favors a B+ tree over a hash table for range queries.
- Trace, in outline, how a real database uses ideas from every unit of this course.
An index is a smaller, faster shadow of the file
A textbook's index page does not contain the book's content — it contains just enough information, page numbers keyed by topic, to find content fast. A file index works the same way: a separate, much smaller structure holding keys and pointers to where full records live in the main file, letting a lookup avoid scanning the file itself entirely.
Why not just use a hash table for the index
A hash table answers 'is this exact key here' about as fast as anything can — but it cannot answer 'give me every record with a roll number between 200 and 350' without checking every possible key in that range one at a time, since hashing deliberately scatters related keys apart to avoid the collisions Lessons 3 and 4 covered.
Unit III Lesson 4's B+ tree does the opposite on purpose: its leaves are linked in sorted order, so once you find the start of a range with one search, you walk straight across to collect the rest — exactly the range-query strength Unit III named as the whole reason B+ trees, not plain B-trees, back real database indexes.
One database row, every unit of this course
Trace what happens when a database answers one query, and every unit of this course appears: the data itself sits in records following Lesson 5's file organization, stored with Lesson 6's binary file mechanics. A B-tree family index from Unit III — often specifically a B+ tree — locates the right records fast. If the query joins data across a relationship, Unit IV's graph traversal ideas are exactly what a query planner uses to decide the cheapest path through the tables involved. And a hash table from this unit's early lessons often backs a fast single-key cache sitting in front of all of it.
None of this was ever really about hash tables in isolation, or B-trees in isolation. It was always about having several tools with different trade-offs and knowing which one a given question actually needs.
Try it yourself
A university system needs to answer both 'what are the details of roll number 12345' and 'list every student with a CGPA above 8.5, sorted' quickly. Name the index type you would build for each, and explain why one index cannot serve both well.
Need a hint?
One question is an exact single-key lookup; the other needs sorted order across a range.
Check the worked solution
Roll-number lookup is a single-key question, ideally served by a hash index — Lesson 1's O(1) average lookup, no ordering needed. The CGPA range-and-sort question needs a B+ tree index on CGPA, using Unit III Lesson 4's linked leaves to walk the range in order directly. A hash index cannot answer the second question without scanning every student, since hashing deliberately destroys the ordering a range query needs; a B+ tree can answer the first question too, just with a few more comparisons than a hash table's direct computation — which is exactly why real systems often build both.
Quick check
Why does a database favor a B+ tree over a hash table specifically for range queries?
Why this lesson exists
Syllabus mapping
Indexing
Maps to course outcomes CO1, CO2, CO4.