Open any database that powers a college library catalogue, a bank’s transaction system, or an e-commerce store, and you will find millions of records sitting in storage. The question that decides whether a search feels instant or painfully slow is simple: does the system have to scan every single row, or can it jump straight to what you need? This is exactly the problem that indexes solve. They are one of the most important tools in physical database design, and understanding them explains why a well-built system answers queries in milliseconds while a poorly designed one keeps users waiting.
Table of Contents
What is an index?
An index is a separate data structure that stores the values of one or more columns along with pointers to the actual rows where those values live. Think of the index at the back of a textbook. Instead of flipping through every page to find a topic, you check the index, read the page number, and go directly there. A database index works the same way: it keeps a sorted, quickly searchable copy of the indexed values so the system can locate records without scanning the whole table.
The performance difference is enormous. Imagine a table where the data spans many storage blocks. Without an index, the database may have to read hundreds of blocks to find a match. With an index, it might read only a handful. One worked example shows that a search needing to read thousands of bytes from the full table can be reduced to reading just over a thousand bytes of compact index entries, making the lookup dramatically faster. Indexes are built using an index table that holds two essential pieces: a search key and a reference pointer to the data block.
This is why indexes matter most in systems with a high read-to-write ratio. A library OPAC (Online Public Access Catalogue), for instance, is searched thousands of times a day but updated far less often. That makes it an ideal candidate for heavy indexing.
Dense and sparse indexes
Before looking at the major types, it helps to know how index entries are distributed. A dense index keeps an entry for every single search key value in the file. This gives the fastest lookups through a simple binary search, but it consumes more space and demands more maintenance during writes. A sparse index, by contrast, stores entries for only some records, typically the first record of each data block. As documented in DBMS literature, a sparse index is more compact, uses less storage, and is easier to maintain during inserts and deletes, at the cost of a small extra step of scanning within a block once the right block is found. A sparse index can only be built on an ordered field.
Types of indexes
Indexes are mainly classified into three categories: primary, secondary, and multilevel. Each serves a different purpose, and choosing the right one is a core skill in database design.
Primary index
A primary index is created on the ordered primary key field of a table. Because primary keys are unique, not null, and have a one-to-one relationship with data blocks, this index offers fast and reliable searching. It is a form of clustered indexing, where the data file itself is physically sorted in the same order as the index. There can be only one primary index per table, simply because data can only be physically sorted one way at a time.
Consider an Employees table sorted by EmployeeID. A query like searching for the employee whose ID is 123 runs quickly because the table is already ordered by that key, so the index can point almost directly to the right block. As explained in DBMS course material, primary indexing is defined on ordered data and its search keys are unique and sorted.
Secondary index
A secondary index, also called a non-clustered index, is built on a column that is not the primary key and may contain duplicate values. The crucial difference is that a secondary index does not control the physical order of the rows. The data stays sorted by the primary key, while the secondary index provides an alternate path to find records by a different attribute.
Returning to the Employees table, suppose users frequently search by LastName. Since the table is physically ordered by EmployeeID, searching by last name would otherwise mean a full scan. Creating a secondary index on LastName solves this. A table can have many secondary indexes, one for each column users commonly search, filter, sort, or join on. Secondary indexes are typically dense, because the underlying data they point to is not sorted on the indexed field. This flexibility comes at a price, since each additional index must be maintained whenever the data changes.
Multilevel index
As tables grow into millions of rows, even the index itself becomes too large to hold conveniently in main memory. Searching a huge single-level index becomes slow. The solution is a multilevel index, which treats the index like data and builds an index on top of it, creating a tree-like structure of progressively smaller levels.
The system searches the smallest top-level index first, which points to a lower level, which finally points to the data block. As multilevel indexing is described, this lets a key lookup or range query on a large table need only a few block accesses instead of scanning a single massive index. In practice, multilevel indexing is implemented using B-Trees and B+ Trees. These structures keep all leaf nodes at the same level and automatically rebalance themselves during insertions and deletions, so performance stays consistent even as data changes.
The power of this design is striking. An academic analysis of the B-tree notes that because of its large fanout, the tree stays very shallow, and with a memory buffer holding the top levels, the system can often reach the desired leaf with merely one or two disk accesses. B+ Trees are especially good at range queries, such as finding all students with marks between two values, because their leaf nodes are linked in sequence.
Trade-offs between speed and update costs
Indexes are not free. This is the single most important lesson in physical database design: every index that speeds up reads adds a cost to writes. The reason is straightforward. When you insert, update, or delete a row, the database must update not just the table but also every index that references the affected column. As database engineers point out, an index occupies extra disk space and must be kept in sync on every data modification, but for read-heavy applications this trade-off is usually worth it.
The cost is also visible at the storage level. Maintaining a B-tree requires additional space compared with un-indexed data, and any kind of index tends to slow down writes because the index structure has to be updated each time data is inserted. Dense indexes feel this most: since they hold an entry for every row, they demand more maintenance and more memory at write time, while sparse indexes carry a lighter burden because they store only a subset of entries.
Finding the right balance
So how do you decide? The guiding principle is to match indexes to actual query patterns. Index the columns that appear most often in WHERE clauses, joins, and sorting operations, and resist the temptation to index everything. A table loaded with unnecessary indexes will read quickly but write slowly, and over time those indexes can become fragmented and bloated, quietly degrading performance until queries mysteriously slow down.
Workload shape matters too. A reporting system that is queried constantly but updated overnight can afford many indexes. A high-volume logging or sensor-data system that captures far more inserts than queries should lean toward fewer indexes, or toward structures tuned for writes. Research on high update rates confirms that for such workloads, index design decisions should be tilted toward optimising updates rather than queries. The art of physical database design lies in reading this balance correctly for each system.
Why this matters in practice
For anyone managing a library system, a research repository, or any large information store, indexes are the difference between a catalogue that responds instantly and one that frustrates users. A primary index on the accession number keeps records organised; secondary indexes on author, title, and subject let patrons search the way they actually think; and multilevel B+ Tree indexes keep all of this fast even when the collection runs into millions of items. The same logic extends to file systems and search engines, which rely on multilevel index blocks to manage huge volumes of stored data. Understanding indexes is not just exam knowledge; it is the foundation of building systems people can actually use.
What do you think? If you were designing the database for your college library, which fields would you index first, and why? And where would you draw the line, deciding that an extra index is no longer worth the slower writes and added storage it brings?
References
- https://www.geeksforgeeks.org/dbms/difference-between-dense-index-and-sparse-index-in-dbms/
- https://www.scaler.com/topics/dbms/indexing-in-dbms/
- https://www.geeksforgeeks.org/dbms/multilevel-indexing/
- https://arxiv.org/pdf/0811.4346
- https://medium.com/@artemkhrenov/database-indexing-strategies-b-tree-hash-and-specialized-indexes-explained-95a3e5e3b632
- https://www.researchgate.net/publication/30815355_B-tree_indexes_for_high_update_rates
- https://www.tutorialspoint.com/dbms/dynamic_multi_level_indexing_with_b_minus_tree_and_b_plus_tree.htm
Leave a Reply