Database Indexing Deep Dive

Without an index, every query scans every row in the table — O(n). With a B-tree index, the database can find any value in O(log n) steps regardless of table size. At a million rows, that's the difference between scanning 1,000,000 rows and traversing 20 tree nodes.

What An Index Is

An index is a separate data structure the database maintains alongside your table. It stores a sorted copy of one or more columns with pointers back to the full row on disk. Think of it like the index at the back of a textbook — a sorted list of terms with page numbers, so you don't have to read the whole book to find what you need.

The database updates the index automatically on every INSERT, UPDATE, and DELETE. You're trading write performance and extra storage space for dramatically faster reads. That tradeoff is almost always worth it for columns you query frequently.

B-Tree Indexes

The B-tree (balanced tree) is the default index type in PostgreSQL, MySQL, and most relational databases. It's a tree where every leaf is the same distance from the root — balanced — which guarantees O(log n) lookup time regardless of how the data was inserted.

-- Creating a B-tree index (default type)
CREATE INDEX idx_users_email ON users (email);

-- Now this query traverses the tree instead of scanning the table
SELECT * FROM users WHERE email = 'alice@example.com';

-- Range queries also use the index efficiently
SELECT * FROM users WHERE created_at > '2024-01-01';

-- ORDER BY on the indexed column is free — data is already sorted
SELECT * FROM users ORDER BY created_at DESC LIMIT 20;

The tree stays balanced automatically as rows are inserted and deleted. Each internal node holds sorted keys and pointers to child nodes. The database follows those pointers down the tree until it hits the leaf nodes, which hold the actual row pointers (or in the case of a clustered index, the row data itself).

How A Query Uses An Index

The difference in execution between a full table scan and an index lookup is dramatic. Without an index, the database reads every page of the table off disk and checks each row. With an index, it traverses the tree and fetches only the rows that match.

EXPLAIN ANALYZE in PostgreSQL shows you exactly which path the query planner chose:

-- Without index: Seq Scan
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;
-- Seq Scan on orders (cost=0.00..4821.00 rows=12 width=64)
--   (actual time=0.042..48.231 rows=12 loops=1)
-- Planning Time: 0.3 ms, Execution Time: 48.4 ms

-- After: CREATE INDEX idx_orders_customer ON orders (customer_id);
EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;
-- Index Scan using idx_orders_customer on orders (cost=0.43..12.47 rows=12 width=64)
--   (actual time=0.021..0.038 rows=12 loops=1)
-- Planning Time: 0.4 ms, Execution Time: 0.1 ms

Same query, same data, 480x faster. That kind of improvement is common when you're adding an index to a column that was previously unindexed on a large table.

When Indexes Help

Indexes earn their keep in specific situations. A WHERE clause filtering on an indexed column is the obvious case — but there are a few others worth knowing.

JOIN conditions benefit enormously from indexes. If you're joining orders.customer_id to customers.id and customer_id isn't indexed, every join forces a full scan of the orders table. Always index foreign key columns.

ORDER BY on an indexed column is essentially free — the data is already sorted. Without the index, the database has to sort the result set in memory or on disk after fetching it, which becomes expensive at scale.

Covering indexes (more on these below) are the fastest case of all — the database never touches the main table at all.

When Indexes Hurt

More indexes is not always better. Every index is a separate data structure that must be updated on every write. A table with 10 indexes pays 10x the write overhead compared to no indexes.

On write-heavy tables — event logs, metrics, audit trails — unnecessary indexes can slow INSERT throughput by a meaningful amount. Benchmark before adding indexes speculatively.

Low cardinality columns are another trap. An index on a boolean column (is_active) with only two distinct values offers almost no selectivity. If half your rows are true and half are false, the index isn't narrowing down much — the database may decide to ignore it and scan anyway.

Composite Indexes

A composite index covers multiple columns. The column order in the index definition matters enormously, and getting it wrong means the index won't be used.

The rule is the leftmost prefix: the index can only be used starting from the leftmost column in the definition.

-- Index on (last_name, first_name)
CREATE INDEX idx_users_name ON users (last_name, first_name);

-- Uses the index: filters on leftmost column
SELECT * FROM users WHERE last_name = 'Smith';

-- Uses the index: filters on both columns
SELECT * FROM users WHERE last_name = 'Smith' AND first_name = 'Alice';

-- Does NOT use the index: skips the leftmost column
SELECT * FROM users WHERE first_name = 'Alice';

When designing a composite index, put the most selective column first, and then consider which query patterns you're optimizing for. A column used in equality filters should typically come before columns used in range filters.

Covering Indexes

A covering index includes every column your query needs — the SELECT list, the WHERE clause, the ORDER BY. When the index covers the query entirely, the database never has to look up the actual row. It satisfies the entire query from the index structure alone.

-- Query: get email and created_at for active users
SELECT email, created_at FROM users WHERE status = 'active';

-- Covering index: all needed columns are in the index
CREATE INDEX idx_users_status_covering ON users (status, email, created_at);

-- EXPLAIN will show "Index Only Scan" — never touches the table
EXPLAIN SELECT email, created_at FROM users WHERE status = 'active';
-- Index Only Scan using idx_users_status_covering on users

Index-only scans are the fastest reads a relational database can do. For hot query paths — dashboards, API endpoints that run constantly — a well-designed covering index can cut response times by an order of magnitude.

Index Selectivity

Selectivity measures how well an index narrows down the result set. A highly selective index on user_id or email might return one row out of a million. A low selectivity index on country might return 50,000 rows out of a million.

The database query planner makes this call automatically. If it estimates that a query will return more than roughly 10-15% of the table's rows, it may skip the index entirely and do a full scan — because the cost of traversing the index plus fetching each row individually exceeds the cost of a sequential read.

High cardinality columns — UUIDs, email addresses, timestamps, phone numbers — benefit most from indexes. Low cardinality columns — booleans, status enums with 3-5 values, country codes — benefit little unless combined with other high-cardinality columns in a composite index.

Common Mistakes

A few mistakes come up repeatedly in production systems.

Indexing every column "just in case" slows down writes and bloats storage without proportionate read gains. Add indexes in response to measured slow queries, not preemptively.

Getting the column order wrong in a composite index is probably the most common mistake. (first_name, last_name) and (last_name, first_name) are entirely different indexes that serve different query patterns.

Forgetting to index foreign keys is a classic oversight. Every JOIN on an unindexed foreign key column results in a full table scan on the child table.

Not using EXPLAIN ANALYZE before and after adding an index means you're flying blind. Confirm the query planner actually uses your index and measure the real improvement.

Key Takeaways

• An index is a sorted auxiliary data structure with pointers back to rows; you trade write overhead and storage for faster reads
• B-tree indexes support equality, range, and ORDER BY queries in O(log n) — the default choice for almost every column you query
• Composite index column order follows the leftmost prefix rule; column order determines which queries benefit
• Covering indexes (index-only scans) are the fastest possible reads — the database never touches the main table
• High cardinality columns (UUIDs, emails) benefit most from indexes; low cardinality columns (booleans, small enums) rarely do
• Every index slows down writes — profile before adding indexes speculatively, especially on write-heavy tables

Next up: blob storage — how systems like S3 store and serve billions of files without a traditional filesystem.