Relational Database Indexes (B-Tree vs Hash)

A database table containing millions of rows is stored on disk across hundreds of thousands of physical pages. When you execute a query filtering records by a specific column, the database engine has no choice but to read every page from disk into memory to check if the filter matches. This causes high CPU and disk I/O load.

To bypass this cost, databases use indexes. An index is an auxiliary data structure that acts as a map, allowing the database to locate rows quickly without scanning the entire table.

However, not all indexes are built the same way. An index optimized for finding a single record by email might be completely useless for finding customers who registered within a specific date range. Backend engineers must understand the underlying data structures of indexes to choose the right types for their query patterns.

---

How an index maps back to physical data files dictates its storage layout and search performance:

Clustered Index (Primary Key Index)

A clustered index determines the physical, sorted order of rows on disk.

• Mechanics: The leaf nodes of a clustered index contain the actual table data rows. Because physical disk blocks can only be sorted in a single order, a database table can have only one clustered index, which is almost always the table's Primary Key.
• Benefit: Range scans on a clustered index are fast because the physical rows reside sequentially next to each other on disk, matching the index order.

Non-Clustered Index (Secondary Index)

A non-clustered index is a separate structure from the physical table files.

• Mechanics: The leaf nodes of a non-clustered index do not contain the actual table data. Instead, they store the indexed column values alongside a row identifier (RID) or the clustered index key (Primary Key), which acts as a pointer to the physical row.
• Benefit: A table can have dozens of non-clustered indexes. However, querying a column via a non-clustered index requires a two-step lookup: first finding the pointer in the index, then fetching the actual row from the main table file. This second step is known as a bookmark lookup or key lookup, which can introduce random disk I/O overhead.

---

The physical layout of the index structure dictates what query operations it can optimize.

1. B-Tree Index (Balanced Tree)

The default index in most relational databases (such as PostgreSQL, MySQL, and SQLite) is a balanced search tree (specifically a B+ Tree variant).

• Internals: Keys are sorted in node pages. Non-leaf nodes act as routers directing searches down to the leaf layer. The leaf nodes contain all keys and their row pointers. Crucially, B+ Trees connect all leaf nodes horizontally using a doubly linked list.
• Complexity: Lookups, insertions, and deletions cost $O(\log N)$ time.
• Strengths: Highly efficient for point lookups, sorting operations (ORDER BY), and range queries (e.g. WHERE age >= 21 AND age <= 35). Once the leaf pointer for 21 is found using binary search, the database can traverse the linked leaves sequentially to read the remaining records, avoiding further tree traversals.

2. Hash Index

A Hash index uses a hash function to map column values directly to array buckets containing pointers to database rows.

• Complexity: Point lookups cost $O(1)$ time in the average case.
• Weaknesses: Completely unsuitable for range queries or sorting. Because hash functions distribute keys randomly across buckets, there is no spatial or sequential ordering. Querying WHERE age > 21 on a Hash index forces the engine to bypass the index and scan the entire table.

---

When executing a query, the planner chooses one of several scan pathways:

• Table Scan / Sequential Scan: The engine reads every disk page in the physical table heap file from top to bottom.
• Index Seek: The engine traverses the index tree structure (from root to leaf) using a search key, reading only the target node pages. This is the fastest way to locate specific rows.
• Index Scan: The engine scans the entire index from left to right (traversing the linked leaves of a B+ Tree). While it reads the entire index, this is often faster than a table scan because index files are much smaller than table files.
• Index-Only Scan (Covering Index): A highly optimized index scan. If a query requests only the columns that are already stored within the index structure itself (e.g., SELECT age FROM users WHERE age > 21 when age is indexed), the database reads only the index file. It does not perform key lookups to fetch the physical data row from disk, saving physical disk seeks.

---

A composite index is an index built on multiple columns, such as CREATE INDEX ON orders (user_id, created_at).

• The Left-to-Right Rule: The database sorts the index first by the left-most column (user_id), and then sorts rows with identical left values by the next column (created_at).
• Query Match Rules: A composite index on (A, B) can satisfy queries filtering on A alone, or A AND B together. However, it cannot satisfy a query filtering on B alone. This is because values in column B are not globally sorted; they are only sorted within the scope of matching values in column A.

---

While indexes speed up reads, they introduce a write cost. Every time a row is inserted, updated, or deleted, the database must modify the main table file and update every index defined on that table.

For B-Trees, this update may force node splits and merges to keep the tree balanced, triggering random disk I/O. Backend systems must avoid over-indexing tables and instead only create indexes that match their application's query profile.

---

• The Ubiquitous B-Tree — Douglas Comer's classic survey explaining the evolution, structure, and variants of B-Trees in database systems.
• Use The Index, Luke — Markus Winand's guide to database indexing for application developers.
• PostgreSQL Index Types — Technical reference detailing standard indexes, including B-Tree, Hash, GiST, GIN, and BRIN.