How Database Indexes Work: B-Trees and Why Your Query Is Slow

Your application feels sluggish. Users are complaining about slow page loads. You trace the problem to a single database query that takes seconds to complete on a table with millions of rows. The difference between this multi-second disaster and a millisecond response is almost always a database index. Without one, the database is forced to read every single row to find what it needs. With the right index, it can pinpoint the data in a handful of operations.

Understanding how indexes work is not just academic. It's a fundamental skill for building scalable software. The dominant technology behind database indexes for decades has been the B-tree^[1], a data structure purpose-built for fast lookups on storage systems like spinning disks and modern SSDs. Mastering its mechanics and tradeoffs is the key to diagnosing and fixing a huge class of performance problems.

The Problem: The Full Table Scan

Imagine a massive table of user data with millions of entries. When you run a query like SELECT * FROM users WHERE email = 'jane.doe@example.com';, how does the database find the correct row? If there's no index on the email column, the database has only one option: a full table scan (often called a sequential scan in PostgreSQL^[2]).

A full table scan is exactly what it sounds like. The database starts at the beginning of the table and reads every single row, one by one, checking if the email column matches 'jane.doe@example.com'. This is the equivalent of searching for a name in a phone book that hasn't been alphabetized. You have to read every entry from start to finish.

The performance cost is directly proportional to the size of the table. For a small table with a few thousand rows, this might be fast enough. For a table with 100 million rows, the database must read all 100 million rows from disk into memory just to find one. This is incredibly inefficient and a primary cause of slow queries in large-scale applications.

The Solution: The B-Tree Index

A B-tree index provides a shortcut. It's a separate, sorted data structure that acts like a highly efficient map, allowing the database to navigate directly to the data it needs without scanning the whole table.^[18] The B-tree was developed by Rudolf Bayer^[3] and Edward McCreight^[4] at Boeing and first described in their 1970 paper, "Organization and Maintenance of Large Ordered Indices"^[5].

The structure is a self-balancing tree designed specifically for systems that read and write large blocks of data, like disk drives.^[19] Its key characteristic is that internal nodes can have a variable number of child nodes within a predefined range. This keeps the tree's height very low, which is critical for performance.

Here’s how a search works, step-by-step:

1. Start at the Root: The search begins at the single root node of the B-tree. The database reads this node (a single data page^[6], typically 4KB or 8KB) from disk into memory.
2. Scan the Node: The root node contains a sorted list of key values (like email addresses) that act as signposts. The database scans these keys to find the range that contains the target value ('jane.doe@example.com'). Associated with each range is a pointer to a child node.
3. Follow the Pointer: The database follows the pointer to the appropriate child node, loading that page from disk into memory.
4. Repeat Until Leaf: This process repeats. The database traverses down the tree, loading one node per level, until it reaches a leaf node.
5. Find the Row Location: Leaf nodes contain the indexed key value ('jane.doe@example.com') and a pointer to the actual row in the main table. In PostgreSQL, this pointer is the ctid, which specifies the physical location of the row data. In MySQL's InnoDB engine, if the index is the primary key, the leaf node contains the entire row's data.^[20]

The height of a B-tree grows logarithmically with the number of entries. This means that even for a table with billions of rows, a B-tree index might only be 4 or 5 levels deep. A query that would have required billions of row reads in a full scan can now find its data by reading only 4 or 5 pages from disk. This is a performance improvement of many orders of magnitude, changing the operation's complexity from linear, O(n), to logarithmic, O(log n)^[7].

A Concrete Example: Indexing a Users Table

Let's make this tangible. Assume we have a users table in PostgreSQL.

CREATE TABLE users (
 id BIGSERIAL PRIMARY KEY,
 first_name TEXT,
 last_name TEXT,
 email TEXT NOT NULL,
 created_at TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

-- Let's imagine this table is populated with 10 million rows.

Now, we run a query to find a specific user by their email address.

EXPLAIN SELECT * FROM users WHERE email = 'user-5000000@example.com';

Without an index on email, the database query planner has no choice. The PostgreSQL EXPLAIN^[8] output would show a plan like this:

 QUERY PLAN
-----------------------------------------------------------------------------------------------------------
 Gather (cost=1000.00..164805.32 rows=1 width=51)
 Workers Planned: 2
 -> Parallel Seq Scan on users (cost=0.00..163804.22 rows=1 width=51)
 Filter: (email = 'user-5000000@example.com'::text)
(4 rows)

The key part is Parallel Seq Scan on users. The database is reading the entire table. On a large table, this is slow.

Now, let's create an index on the email column using the CREATE INDEX^[9] command.

CREATE INDEX idx_users_on_email ON users(email);

After the index is built, we run the exact same EXPLAIN command again. The query plan will look dramatically different:

 QUERY PLAN
-----------------------------------------------------------------------------------------------------------
 Index Scan using idx_users_on_email on users (cost=0.56..8.58 rows=1 width=51)
 Index Cond: (email = 'user-5000000@example.com'::text)
(2 rows)

The plan has changed to an Index Scan. Instead of scanning the whole table (costing 164805.32 in this example), the database uses the idx_users_on_email B-tree to find the row almost instantly (costing 8.58). The cost units are arbitrary but their relative values are what matter. The indexed query is thousands of times cheaper and faster.^[21]

The Tradeoffs: The Real Cost of an Index

Indexes are not free. They provide huge benefits for read performance, but they come with significant costs that every engineer must weigh.^[21]

Write Penalty

While indexes speed up SELECT queries, they slow down data modification operations: INSERT, UPDATE, and DELETE. Every time a row is added to the table, a corresponding entry must be added to each of its indexes. If you update a value in an indexed column, the index must be updated to reflect the new value's sorted position. This might involve simply updating a leaf node or could trigger more complex operations like node splits and rebalancing the tree, which adds I/O and CPU overhead to write operations. A table with five indexes will require six writes for every INSERT: one for the table itself and one for each index.

Storage Cost

Indexes are data structures that live on disk, just like your tables. They consume space. The exact size depends on the columns being indexed. An index on a 64-bit integer will be much smaller than an index on a 255-character text field. For very large tables, multiple indexes can easily double the total disk space required for your data.^[18] This has direct cost implications for storage and backups.

Maintenance Overhead

As data is updated and deleted, indexes can become fragmented or bloated, just like the tables themselves. This means they may contain empty space or not be optimally structured, which can degrade performance over time. Databases require periodic maintenance operations, like PostgreSQL's REINDEX or VACUUM, to rebuild or clean up indexes and maintain their efficiency.

Why Your Index Isn't Being Used (Or Is Still Slow)

Sometimes you create an index, but the query planner ignores it. This is a common source of confusion. The planner is a cost-based optimizer; it will only use an index if it calculates that doing so is cheaper than a full table scan.

Low Cardinality

Cardinality^[10] refers to the number of distinct values in a column. An index on a high-cardinality column (like a unique email or user_id) is very effective. An index on a low-cardinality column (like a status column with values 'active', 'inactive', 'pending') is often useless. If the database needs to retrieve all 'active' users, and 'active' represents 80% of the table, it's far more efficient to just scan the whole table once than to jump back and forth between the index and the table for 80% of the rows.

Function Wrapping

An index on email will not be used by the query WHERE lower(email) = 'jane.doe@example.com'. The database cannot use the index because it is sorted by the raw email values, not the result of the lower() function. The solution is to create an index that matches the query. Most modern databases support expression-based indexes^[11]: CREATE INDEX ON users (lower(email));.

Composite Index Column Order

For queries that filter on multiple columns, you can create a composite (or multicolumn) index^[12]. For example: CREATE INDEX ON users (last_name, first_name);. The order of columns is critical. This index is sorted first by last_name, and then by first_name for users with the same last name. It can efficiently handle queries with WHERE last_name = 'Smith' or WHERE last_name = 'Smith' AND first_name = 'John'. However, it cannot be used effectively for a query with WHERE first_name = 'John', because the index isn't sorted by first name first.

The LIKE Trap

A B-tree index can be used for LIKE queries, but only if the wildcard is not at the beginning of the string. A query WHERE name LIKE 'Smith%' can use an index on name because it can seek to the 'Smith' section of the index and scan from there. A query WHERE name LIKE '%Smith' cannot use the index, because the leading wildcard means the matching values could be anywhere in the index, forcing a full scan.

Common Misconceptions

"More indexes are always better."

This is false. As discussed, every index imposes a penalty on writes (INSERT, UPDATE, DELETE) and consumes disk space. Over-indexing is a common performance anti-pattern, especially in write-heavy systems. Indexes should be added deliberately to support specific, frequent, and slow queries.

"Primary keys are magically fast."

Primary keys are fast because they are, by definition, indexed. A primary key constraint automatically creates a unique index. There is no magic involved. In some systems like the MySQL InnoDB^[13] storage engine, the primary key has a special status. It defines the table's physical layout via a clustered index, where the table data is stored in the leaf nodes of the primary key's B-tree. This makes primary key lookups extremely fast. In PostgreSQL, the primary key is just a unique index, and the table data is stored separately in a structure called a heap, making secondary indexes just as performant as the primary key index for lookups.^[20]

"Indexes make all queries on a column faster."

Indexes only accelerate queries that can take advantage of their sorted order for lookups or range scans. A query that processes every row of a table (like calculating an average over the entire dataset) will not benefit from an index and will likely perform a full table scan anyway.

The B-Tree Family and Modern Alternatives

Most relational databases technically use a B+ tree^[14], a key variant of the B-tree. In a B+ tree, all values (or pointers to rows) are stored only in the leaf nodes. Additionally, the leaf nodes are linked together in a doubly-linked list. This structure is highly optimized for range scans, such as WHERE age > 30, because once the database finds the first entry for age 30, it can just scan along the linked list of leaf nodes to find all subsequent entries without traversing back up the tree.

While B-trees are the default and most common index type, specialized workloads may call for other index structures that databases like PostgreSQL provide:

• Hash Indexes^[15]: Optimized only for simple equality comparisons (=). They can sometimes be faster than B-trees for this specific case but do not support range queries.
• GIN (Generalized Inverted Index)^[16]: Ideal for indexing composite types, like the elements of an array or the keys of a JSONB document. It's the powerhouse behind efficient full-text search and JSON querying.
• GiST (Generalized Search Tree)^[17]: A framework for building indexes over complex data types like geometric data (finding all points within a polygon) and full-text search.
• BRIN (Block Range Index): Designed for very large tables where data has a natural correlation with its physical storage location (like a timestamp column in a log table). They are much smaller than B-trees but less precise.

The Technical Leader's Decision Lens

As a technical leader or senior engineer, you don't need to design B-trees, but you do need a framework for using them effectively. The core decision is always balancing the read performance gains against the write performance and storage costs.

Use an iterative, evidence-based approach to indexing:

1. Observe: Use your database's query analysis tools (EXPLAIN ANALYZE in PostgreSQL) and monitoring systems (like Amazon RDS Performance Insights) to identify the most frequent and expensive queries. Look for long-running queries dominated by sequential scans.
2. Hypothesize: Based on a slow query's WHERE, JOIN, and ORDER BY clauses, propose a specific index. Consider column order for composite indexes and the column's cardinality. Ask: "Will this query's filter be selective enough for an index to be worthwhile?"
3. Test: Never add indexes directly to a production database. Create the index in a staging environment that mirrors production data and traffic patterns. Benchmark the target query to confirm it's faster and uses the new index. Crucially, also measure the performance impact on your application's key write operations (INSERT, UPDATE).
4. Deploy and Monitor: Once validated, deploy the index to production during a low-traffic period. Monitor key application metrics, database CPU, I/O, and write latency to ensure there are no negative side effects.

Indexing is not a one-time setup. It's a continuous process of optimization as your application's data and query patterns change. By understanding the fundamental mechanics of how indexes work, you can make informed, data-driven decisions that keep your application fast and scalable.