Picture flipping through a thousand-page textbook looking for every mention of a specific term, but the book has no index at the back, only page after page of plain text. The only option is to read the entire book from cover to cover, checking every single page. Now picture the same search with a proper index at the back of the book, listing the term alphabetically alongside the exact page numbers where it appears. The difference in effort between these two scenarios is enormous, and it is exactly this same difference that database indexing brings to searching through millions of rows of data.
Without an index, a database searching for a specific row must perform what is called a full table scan, examining every single record in a table one at a time until it either finds a match or reaches the end of the table. For a table with a handful of rows, this barely matters, but for a table holding millions of records, a full table scan can take an unacceptably long time. An index provides a much faster path to the exact data being searched for, similar in spirit to a book's index, at the cost of some extra storage space and some overhead whenever the underlying data changes.
In this tutorial, you will learn what a database index is, the distinction between ordered and unordered files, primary and secondary indexes, clustering indexes, and the important difference between dense and sparse indexes, along with a look at multilevel indexes. Worked examples are included throughout to make each type of index concrete.
An index is a separate data structure, stored alongside the actual table, that maps values of one or more columns, often called the search key, to the physical location of the corresponding records within the table. Rather than scanning the entire table, the database consults the index first, quickly narrowing down exactly where the desired records are physically stored, and then retrieves only those specific records directly.
| Without an Index | With an Index |
|---|---|
| Search the entire table, row by row, checking every record for a match. | Look up the search key in the compact index, then jump directly to the matching record's location. |
| Time grows proportionally with the total number of rows in the table. | Time grows much more slowly, often logarithmically, as the number of rows increases. |
Indexes that speed up searches on the specific column a file is physically sorted by are called ordering indexes, and understanding them requires first understanding what it means for a file to be ordered in the first place. In an ordered, or sequential, file, all the records are physically stored on disk sorted according to the value of one particular field, called the ordering field.
EmployeeID Name Department 1001 Aditi Sales 1002 Rohan Marketing 1003 Kavya Finance 1004 Aman Sales 1005 Priya IT
Here, the file is physically sorted by EmployeeID, making EmployeeID the ordering field. An index built specifically on this ordering field is what allows for the two important categories discussed next: primary indexes and clustering indexes.
A primary index is built on the ordering field of a file, where that ordering field is also the primary key of the table, guaranteeing a unique value for every single record. Because the file is sorted by this key, and each key value is unique, a primary index typically contains just one index entry for every block of records stored on disk, rather than one entry for every single record.
Data File (sorted by EmployeeID, 2 records per disk block): Block 1: 1001 Aditi, 1002 Rohan Block 2: 1003 Kavya, 1004 Aman Block 3: 1005 Priya, 1006 Nikhil
Primary Index: EmployeeID Block Pointer 1001 → Block 1 1003 → Block 2 1005 → Block 3
To find EmployeeID 1004, the database consults the primary index, sees that 1004 falls between the entries 1003 and 1005, follows the pointer for 1003 to Block 2, and then searches only within that small block for the exact matching record, avoiding the need to scan Block 1 or Block 3 at all.
A clustering index is also built on the ordering field of a file, but unlike a primary index, the ordering field here is not necessarily unique, meaning multiple records can share the same value. This situation arises whenever a table is physically sorted by a non-key field, such as sorting employee records by department rather than by employee ID.
Data File (sorted by Department): Finance: 1003 Kavya IT: 1005 Priya Marketing: 1002 Rohan Sales: 1001 Aditi, 1004 Aman
Clustering Index: Department Block Pointer Finance → first record with Department = Finance IT → first record with Department = IT Marketing → first record with Department = Marketing Sales → first record with Department = Sales
Since Department is not unique, the clustering index only needs to point to the very first record for each distinct department value, since all records sharing that value are guaranteed to be stored physically together, right next to each other, thanks to the file's sorted order.
A secondary index is built on a field that is not the ordering field of the file, meaning the file is not physically sorted according to this particular field at all. Because the underlying records are scattered throughout the file with no particular order relative to this field, a secondary index must contain one entry for every single record, rather than one entry per block, since there is no guarantee that matching records will be stored anywhere near each other.
Data File (still physically sorted by EmployeeID, as in the primary index example): Block 1: 1001 Aditi Sales, 1002 Rohan Marketing Block 2: 1003 Kavya Finance, 1004 Aman Sales Block 3: 1005 Priya IT, 1006 Nikhil Sales
Secondary Index on Department: Department Record Pointer Finance → 1003 IT → 1005 Marketing → 1002 Sales → 1001 Sales → 1004 Sales → 1006
Notice that "Sales" appears three separate times in this secondary index, once for each matching record, since the records themselves are scattered across Block 1, Block 2, and Block 3, with no guarantee of being physically adjacent, unlike the clustering index example above where all Sales records happened to be grouped together.
Indexes can also be classified by exactly how many entries they contain relative to the underlying data, a distinction that applies across primary, clustering, and secondary indexes alike.
| Type | Description |
|---|---|
| Dense Index | Contains one index entry for every single search key value present in the data file, guaranteeing a direct pointer to every record. |
| Sparse Index | Contains index entries for only some of the search key values, typically one entry per disk block rather than one per record. |
Data File (sorted by EmployeeID, 2 records per block): Block 1: 1001, 1002 Block 2: 1003, 1004 Block 3: 1005, 1006 Dense Index: 1001 → Block 1 1002 → Block 1 1003 → Block 2 1004 → Block 2 1005 → Block 3 1006 → Block 3 Sparse Index: 1001 → Block 1 1003 → Block 2 1005 → Block 3
The dense index takes up more storage space, since it has an entry for every single record, but it can directly locate any record without needing to search within a block afterward. The sparse index is more compact, but locating a specific record requires an additional small search within the target block once the index has narrowed down which block to examine, exactly as demonstrated earlier in the primary index example.
A secondary index is almost always dense, since it must contain an entry for every record it needs to locate, given that matching records are not guaranteed to be grouped together physically, unlike primary and clustering indexes, which are often sparse, since the underlying file's own sorted order already does most of the organizational work.
As a table grows extremely large, even a sparse first-level index can itself become too large to search through efficiently, or even too large to fit comfortably in memory all at once. A multilevel index addresses this by treating the first-level index itself as an ordered file, and building a second, even smaller index on top of it, and potentially further levels beyond that, forming a hierarchy.
First-Level Index (sparse, one entry per block of the data file): 1001, 1101, 1201, 1301, 1401, 1501, 1601, 1701 ... Second-Level Index (built on top of the first-level index): 1001 → points to the block of the first-level index containing 1001 through 1301 1401 → points to the block of the first-level index containing 1401 through 1701
Searching for a record now involves first consulting the small, easily searched second-level index to narrow down which portion of the first-level index to examine, then consulting that portion of the first-level index to find the correct block of the actual data file, and finally searching within that block for the target record. This hierarchical narrowing is exactly the same fundamental idea used by the B+ tree structure covered in the next chapter, which formalizes and generalizes multilevel indexing into one of the most widely used data structures in real database systems.
| Index Type | Built On | Key Uniqueness | Typical Density |
|---|---|---|---|
| Primary Index | Ordering field that is also the primary key. | Unique | Sparse |
| Clustering Index | Ordering field that is not the primary key. | Not necessarily unique | Sparse |
| Secondary Index | A field that is not the ordering field. | May or may not be unique | Dense |
Indexing represents one of the most impactful performance decisions in real database design, since well-chosen indexes can turn a slow query taking several seconds into one completing in a fraction of a second, particularly on tables containing millions of rows. This benefit does come with tradeoffs, however, since every index must itself be updated whenever the underlying data changes, meaning insertions, deletions, and updates all become somewhat slower on heavily indexed tables, which is why database designers must carefully balance how many indexes to create against how often the underlying data is modified.
| Mistake | Correct Understanding |
|---|---|
| Confusing a primary index with a clustering index. | A primary index is built on a unique ordering field, typically the primary key, while a clustering index is built on a non-unique ordering field. |
| Assuming a secondary index can be sparse. | Secondary indexes must generally be dense, since matching records are not physically grouped together, unlike primary and clustering indexes. |
| Believing more indexes always improve overall database performance. | Indexes speed up searches but slow down insertions, deletions, and updates, so excessive indexing can hurt performance on write-heavy tables. |
| Thinking a multilevel index requires re-searching the entire first-level index every time. | A multilevel index uses higher levels specifically to narrow down which small portion of the lower level needs to be searched, avoiding a full scan of the first-level index. |
Indexing transforms searching through a database from a slow, exhaustive scan of every record into a fast, targeted lookup, much like using a well-organized index at the back of a large textbook. Through primary, clustering, and secondary indexes, the important dense versus sparse distinction, and the hierarchical structure of multilevel indexes, this chapter demonstrated exactly how databases organize auxiliary structures to dramatically speed up data retrieval, using a single consistent employee table example throughout.
In this tutorial, you learned what an index is and why it matters, the difference between primary and clustering indexes built on a file's ordering field, why secondary indexes must generally be dense, and how multilevel indexes handle very large tables efficiently. With this foundation, you are ready to move on to the B+ tree, the specific data structure that most real-world database systems actually use to implement efficient, balanced multilevel indexing in practice.