The Role of Data Structures in Database Indexing

Flip to the back of any thick textbook and you will find an index: a list of terms with page numbers, sorted alphabetically so you never have to read the whole book to find one fact. Databases face the same problem at a much bigger scale. A table with a few million rows cannot be scanned row by row every time someone runs a query. The solution borrows the same idea as the book index, except it is built using specific data structures designed to make searching, sorting, and retrieving records almost instant.

Why databases need an index in the first place 🔗

Without an index, a database has only one option when you ask for a specific record: check every single row until it finds a match. This is called a full table scan, and it works fine for a few hundred records. It becomes painfully slow once a table holds millions of rows, because every lookup means reading data from disk, and disk access is far slower than reading from memory.

An index solves this by creating a separate, compact structure that stores the values of a chosen column along with a pointer to where the full record actually lives. Instead of scanning the whole table, the database searches this smaller, organised structure first and jumps straight to the right location. This structure is essentially a lookup table, built once and then maintained automatically as data changes.

Inside the B-tree: the default indexing engine 🔗

Most relational databases, including MySQL, PostgreSQL, Oracle and SQL Server, use a data structure called the B-tree as their default index type. The name stands for balanced tree, and that single word explains most of its value.

How a B-tree finds a record 🔗

A B-tree organises index entries into nodes, each holding several keys arranged in sorted order. A search starts at the root node and compares the target value against the keys stored there. Based on that comparison, the search moves down to the correct branch, skipping every other branch entirely. Each node is typically sized to match a disk page, which means one node can hold dozens or hundreds of keys, and very few disk reads are needed to reach the answer.

Why balance keeps searches fast 🔗

Every leaf in a B-tree sits at exactly the same depth from the root. This balance guarantees that a search, insertion, or deletion takes roughly the same number of steps no matter which record is being looked for. Real-world indexes holding millions of records typically need a tree depth of only four or five levels to reach any record, which is why B-tree lookups feel instantaneous even on huge tables. The technical term for this efficiency is logarithmic time complexity, written as O(log n): as the table grows from a thousand rows to a billion, the number of steps needed to find a record grows extremely slowly in comparison.

B-trees have one more advantage that makes them the default choice: because the keys are stored in sorted order, they handle range queries naturally. A request for “all orders placed between two dates” or “all salaries above a certain amount” can be answered by walking along the sorted keys, something a purely random structure cannot do.

Hash indexes: built for speed, not for range 🔗

Not every query needs sorted data. Sometimes a system only needs to check whether a value matches exactly, such as looking up a user by their unique ID. For this narrow but common case, some databases offer a hash index.

A hash index runs the indexed value through a hash function, which converts it into a fixed location in a table of “buckets.” Hash indexing works best for equality comparisons and is not suited to range queries or partial matches. Because there is no scanning or comparing involved, an exact-match lookup can be resolved in constant time, regardless of how large the table grows.

The trade-off is flexibility. A hash index cannot answer “greater than,” “less than,” or “starts with” queries, because hashed values carry no information about their original order. Two very different values can also produce the same hash location, known as a collision, which the database has to resolve using additional logic, adding a small amount of overhead.

Organising indexes: primary, secondary and clustered structures 🔗

Beyond the underlying data structure, indexes are also classified by how they relate to the actual table data.

Primary index: This is built automatically on the table’s primary key. It usually determines the physical order in which rows are stored on disk, which is why it is also called a clustered index.

Clustered index: A table can have only one clustered index, since data can physically exist in only one order at a time. Because it defines the actual arrangement of rows on disk, this index type is especially efficient for range-based queries, such as pulling all transactions from a particular month.

Secondary index: Built on any column other than the primary key, a secondary index does not change how rows are physically stored. Instead, it keeps its own sorted structure of values with pointers back to the original rows. A table can have several secondary indexes, letting the same data be searched efficiently by different attributes, such as email, city, or department.

This layered approach mirrors how a well-run office keeps multiple indexes for the same set of files: one by employee ID for payroll, another by department for administration, and another by date for audits. The underlying records do not move; only the lookup structure changes.

The trade-off no index escapes 🔗

Indexes are not free. Every index consumes additional storage space, since it duplicates the indexed column’s values alongside pointers to the original data. More importantly, every insert, update, or delete on the table has to update every index built on it, which slows down write operations. A B-tree simplifies the binary search tree by allowing each node to hold more than two children, which keeps the structure shallow, but the database still has to do real work to keep that structure balanced after every change.

This is why database administrators do not index every column. The general rule is to index columns that are frequently searched, filtered, or joined on, while leaving rarely queried columns unindexed. A table with too many indexes can end up slower overall, because the cost of maintaining them during writes outweighs the benefit during reads.

Why this matters beyond the exam 🔗

Indexing is not just database theory; it is the invisible engine behind almost every digital records system used in modern offices, from HR management software to e-commerce order tracking. When a company handles thousands of customer records, invoices, or employee files digitally, the speed at which a clerk or manager can retrieve a specific record depends entirely on how well that underlying data is indexed. Understanding the logic behind indexing data structures helps in appreciating why some office software feels instant while poorly designed systems feel sluggish as data grows.

What do you think? If you were designing a records system for a growing organisation, which columns would you choose to index first, and why? Can you think of examples where a range-friendly B-tree index would work better than a fast but rigid hash index?

References

1. https://www.tutorialspoint.com/dbms/dbms_indexing.htm
2. https://planetscale.com/blog/btrees-and-database-indexes
3. https://use-the-index-luke.com/sql/anatomy/the-tree
4. https://www.geeksforgeeks.org/dbms/difference-between-indexing-techniques-in-dbms/
5. https://www.jaroeducation.com/blog/indexing-in-dbms-explained
6. https://builtin.com/data-science/b-tree-index