Database Indexing

The Problem Indexes Solve

Imagine a 100 million row table of users. You ask for the user whose email is [email protected]. Without an index, the database has only one option: read every single row, check each email, return when it finds a match. This is called a full table scan. On 100 million rows, it might take 30 seconds or several minutes. The user has long since closed the browser tab.

An index is a separate data structure that lets the database find rows by a specific column without scanning the whole table. With the right index, that same query takes a few milliseconds. The same lookup over the same hardware. Six orders of magnitude faster.

Think of indexes like the index at the back of a book. Instead of reading every page to find "Atomicity," you flip to the index, find the entry, and jump straight to page 47. The book is no smaller. You just bypassed reading 99% of it.

Indexes are arguably the single biggest determinant of database performance. They are also one of the most misunderstood. This article walks through every major index type, when to use them, and how to know if your indexes are actually helping.

Step 1: The Fundamental Trade-off

Indexes are not free. They have a cost. Understanding that cost is the foundation of using them well.

What Indexes Cost

Storage. An index is a separate data structure on disk. A typical B-tree index is 10-20% the size of the indexed column. A table with 5 indexes might be 50-100% bigger on disk than the same data without indexes.

Write latency. Every INSERT, UPDATE, and DELETE has to update not just the row but every index that includes the affected columns. A table with 5 indexes has roughly 5x the write cost of a table with no indexes.

Memory pressure. Hot indexes live in memory. Indexes you don't use still take buffer pool space if they happen to be touched. This crowds out the data the database actually needs in memory.

Maintenance. Indexes can fragment over time. Some databases require periodic rebuilds. Some indexes have specific maintenance requirements (e.g., GIN indexes in Postgres).

What You Get

Reads can be hundreds or thousands of times faster, especially on filter columns and join columns. The right index turns a 30-second query into a 10-millisecond one. That single change might make a feature feasible that wasn't before.

The Rule of Thumb

Only index columns you actually query and filter on. Indexing every column "just in case" is the most common mistake new database operators make. It piles cost on writes for no read benefit. Run with no indexes. Add them when EXPLAIN shows you a slow query that an index would help.

Step 2: B-Tree Indexes (The Default)

Used by Postgres, MySQL, Oracle, SQL Server, and most relational databases. The "B" stands for "balanced." It's a tree structure where every leaf node is at the same depth from the root. This guarantees consistent lookup performance regardless of which value you query.

How B-Trees Work

Each node holds a sorted range of keys plus pointers to child nodes. To find a value, start at the root, compare your value to the keys in the node, follow the pointer to the appropriate child, repeat until you reach a leaf, which contains a pointer to the actual row data.

At each step, you eliminate roughly half (or more) of the remaining tree. This gives O(log N) lookups. For 100 million rows, that's about 27 comparisons instead of 100 million. Reads complete in microseconds.

What B-Trees Excel At

Equality lookups. WHERE id = 5. Direct path through the tree.
Range queries. WHERE created_at > '2026-01-01'. The keys are sorted, so range scans are efficient.
Ordering. ORDER BY name. The index already provides sorted output.
Prefix matches on text. WHERE name LIKE 'A%'. Match the prefix, scan all matching keys.
Combination filters. Composite indexes work cleanly when filtering on the leading columns.

What B-Trees Cannot Do Well

Substring matches. WHERE name LIKE '%apple%'. The leading wildcard means no prefix to match. Full scan.
Full-text search. Find me documents about a topic. Different problem; needs a different index type (covered later).
Negation. WHERE status != 'active'. Often forces a full scan because excluded values can be anywhere.

Why B-Trees Win Most of the Time

B-trees handle the vast majority of real-world query patterns. Equality, range, ordering, prefix all work. The structure is well-understood, well-implemented, and stable. It is the right default index for almost all relational workloads.

Step 3: Hash Indexes

A hash table stored on disk. Hash the key, jump to the slot, return the row pointer. Lookups are O(1) instead of O(log N).

What Hash Excels At

Exact equality lookups. Slightly faster than B-trees for the simplest case. The constant-time guarantee is mathematically appealing.

What Hash Cannot Do

Range queries: hash distribution scrambles ordering. WHERE id BETWEEN 100 AND 200 requires touching every slot.
Ordering: ORDER BY name doesn't work; the index is unsorted.
Prefix matches: same problem; ordering matters.

When Hash Indexes Are Used

Redis is essentially one giant hash index. The whole engine is built around hash-keyed data with O(1) lookups.
Postgres has hash indexes as a special index type but rarely uses them; B-trees are nearly always preferred. Modern Postgres has WAL support for hash indexes (which it didn't always), but the use case is narrow.
Most key-value stores (DynamoDB partition lookups, Memcached) use hashing internally.

For most relational workloads, B-trees beat hash because B-trees handle range queries while still doing equality fast. Hash indexes are a niche optimization.

Step 4: LSM-Tree Indexes

Used by Cassandra, RocksDB (which powers many things including MyRocks, TiKV, CockroachDB's storage layer), LevelDB, ScyllaDB. Optimized for write-heavy workloads.

How LSM-Trees Work

Writes go to an in-memory sorted structure called a memtable. Memtable writes are extremely fast because they happen in memory.

When the memtable reaches a size threshold, it gets flushed to disk as an immutable, sorted file called an SSTable (Sorted String Table). The SSTable is written sequentially (no random I/O) and never modified after creation.

Over time, you accumulate many SSTables. Reads must check the memtable first, then SSTables newest to oldest. This gets slow if you have hundreds of SSTables, so a background process called compaction merges old SSTables into fewer, larger ones.

Why LSM-Trees Are Good for Writes

Writes never touch disk on the hot path (just memory). Disk writes are sequential (much faster than random). No update-in-place: every write is an append. This combination produces the highest write throughput of any common index.

Cassandra and similar databases can absorb hundreds of thousands of writes per second per node. B-tree systems would tap out long before that.

The Trade-offs

Reads can be slower. Multiple SSTables must be checked. Bloom filters help (skip SSTables that don't contain the key) but read amplification is still real.
Compaction consumes resources. CPU and IO for the background merge. Tuning compaction is non-trivial.
Tombstones. Deletes are markers that say "this key is gone," not actual removal. Old data lingers until compacted.
Space amplification. Multiple copies of overlapping data exist briefly during compaction.

When LSM Beats B-Tree

Time-series data (sensor readings, log events). Append-heavy workloads. Workloads where you can tolerate slightly slower reads in exchange for much faster writes.

When B-Tree Beats LSM

Read-heavy workloads where every read must be fast. Random update patterns where compaction overhead is wasted work.

Step 5: Inverted Indexes (Full-Text Search)

Used by Elasticsearch, Solr, Lucene. The basis of all full-text search.

How Inverted Indexes Work

For each unique word (token) in the corpus, store a list of document IDs that contain that word.

Document 1: "the quick brown fox"
Document 2: "the lazy dog"

The inverted index becomes:

"the"   -> [1, 2]
"quick" -> [1]
"brown" -> [1]
"fox"   -> [1]
"lazy"  -> [2]
"dog"   -> [2]

Searching "lazy fox" means: look up "lazy" → [2], look up "fox" → [1], intersect → empty. No documents contain both. Searching "fox" → [1].

What Makes It Powerful

Tokenization, stemming (find -> finding), stop word removal, scoring (TF-IDF, BM25), proximity, fuzzy matching. Full-text engines layer many capabilities on top of the basic inverted index.

When to Use

Searching documents by their content (blog posts, product descriptions, support articles). Faceted search with filters. Anything users would type into a search box. Modern relational databases have varying degrees of full-text support; specialized engines like Elasticsearch are usually preferred for substantial workloads.

Step 6: Other Specialized Indexes

R-Tree / Spatial Indexes

For geographic queries. "Find restaurants within 1km of this point." PostGIS in Postgres uses these. They organize 2D or 3D space hierarchically; queries efficiently prune large regions of the space.

Bitmap Indexes

For low-cardinality columns (gender, status, category). Stores a bit per row per value. Queries on multiple low-cardinality columns can be combined with AND/OR on bitmaps; very fast.

Common in data warehouses (analytics workloads with lots of categorical filtering). Less common in OLTP because updates require rewriting bitmaps.

BRIN (Block Range Index)

Postgres-specific. Tiny indexes for naturally ordered data, like time-series. Instead of indexing every row, BRIN stores min/max values per block (e.g., per 128 pages). Queries skip blocks whose min/max can't match.

Tradeoff: imprecise. May read many rows that don't match. Best when data is naturally ordered (created_at columns) and the table is huge.

GIN and GiST Indexes

Postgres index types for complex data. GIN (Generalized Inverted Index) for arrays, JSON keys, full-text. GiST (Generalized Search Tree) for spatial, ranges, custom types.

If you need to query "give me rows where the JSON column contains key X" or "rows whose tags array includes Y," these are how Postgres makes that fast.

Step 7: When to Use What

Step 8: Composite Indexes

An index on a single column is the simplest case. Composite (multi-column) indexes index on multiple columns at once.

CREATE INDEX idx_name ON users (last_name, first_name);

How They Work

The index is sorted first by the leading column (last_name), then within ties by the next column (first_name). Think of it like a phonebook: sorted by last name, then by first name.

Which Queries Benefit

WHERE last_name = 'Smith' uses the index efficiently.
WHERE last_name = 'Smith' AND first_name = 'John' uses both columns of the index.
WHERE last_name = 'Smith' ORDER BY first_name is essentially free; the index is already in the right order.

Which Queries Cannot Use It

WHERE first_name = 'John' alone cannot use this index. The index is sorted by last_name first; first_name is unsorted across the index. The query falls back to a full table scan unless a separate index on first_name exists.

This is the leftmost prefix rule. A composite index helps queries that filter on its leading columns, in order. Skip a column and the index becomes useless for the rest.

Choosing Column Order

Put the most selective column first when possible. Columns used in equality filters before columns used in ranges. Columns commonly used together stay close in the index.

This decision matters a lot. A wrong order means the index might exist but never get used.

Step 9: Covering Indexes

An index that contains all the columns a query needs. The query never has to touch the actual table; it gets everything from the index. This is called an index-only scan and is the fastest possible query.

Example

-- Query
SELECT first_name, last_name FROM users WHERE last_name = 'Smith';

-- Without covering: index returns row pointers, then DB reads each row.
CREATE INDEX idx_last ON users (last_name);

-- With covering: index has both columns, no table read needed.
CREATE INDEX idx_covering ON users (last_name, first_name);

How Different Databases Handle It

Postgres: any composite index where you query for columns within the index is covering. Plus the special INCLUDE clause for adding columns to the leaf without affecting sort order.
MySQL InnoDB: primary key is the row data. Secondary indexes always include the primary key implicitly. So secondary indexes that include the primary key are "covering" for primary-key columns.
SQL Server: explicit INCLUDE clause for non-key columns in the index leaf.

When to Use

Hot read paths where you need extreme speed. Add the read columns into the index so the table never gets touched. Trade storage for speed.

Step 10: How to Spot a Bad Index

Use EXPLAIN (Postgres, MySQL) or the equivalent in your database. EXPLAIN shows what the query planner intends to do.

Look For Warning Signs

Seq Scan / Full Table Scan. The query reads every row. Either no useful index exists, or the planner decided the scan is faster than using an index (which itself is sometimes correct for small tables or non-selective filters).

High filter rows ratio. The plan says "Index Scan: 1,000,000 rows examined, 10 returned." The index returned a million rows just to find 10 matches. The index is too broad. A more selective index (or composite) would help.

Sort steps. The query plan includes a separate Sort node. An index in the right order might eliminate it.

Hash Join over Nested Loop. The planner chose hash join because it doesn't think your index is selective enough. Sometimes correct, sometimes not.

Example EXPLAIN Output (Postgres)

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 42;

Seq Scan on orders  (cost=0.00..18334.00 rows=1 width=128)
  Filter: (customer_id = 42)
  Rows Removed by Filter: 999999

Bad. Full table scan, removed 999,999 rows. Need an index on customer_id.

After adding CREATE INDEX idx_customer ON orders (customer_id);:

Index Scan using idx_customer on orders (cost=0.42..8.44 rows=1 width=128)
  Index Cond: (customer_id = 42)

Index used. Microseconds. Fixed.

Tracking Index Usage

Postgres tracks index usage in pg_stat_user_indexes. Indexes with zero scans for months are dead weight; drop them.

MySQL has information_schema.INDEX_STATISTICS with similar data.

Check periodically. Indexes accumulate over time. Many production systems carry indexes nobody has used in years.

Step 11: Index Storage and Maintenance

Disk Space

An index is a copy of the indexed columns plus pointers to rows, organized into the chosen structure. Approximate sizes:

B-tree on a 4-byte integer column: roughly 12-16 bytes per row.
B-tree on a 50-byte VARCHAR: roughly 60 bytes per row.
Composite index on (4-byte int, 50-byte VARCHAR): roughly 65 bytes per row.

For 10 million rows, a typical B-tree index on an integer is 100-150 MB. Multiple indexes accumulate quickly.

Memory and Buffer Cache

Indexes need to live in memory for fast access. Hot pages of an active index get cached in the database's buffer pool. If indexes are too big for memory, lookups get slower because tree traversal hits disk.

This is why "more indexes = always better" is wrong. Each index competes for memory.

Fragmentation and Rebuilding

Over time, B-trees fragment due to inserts/deletes/updates. Pages become sparsely filled. Tree depth grows. Performance gradually degrades.

Maintenance: VACUUM in Postgres, OPTIMIZE TABLE in MySQL, periodic index rebuilds. Modern databases auto-vacuum but heavy workloads may need explicit tuning.

Adding Indexes on Live Tables

Adding an index to a multi-billion row production table is non-trivial. The default CREATE INDEX can lock the table for minutes or hours.

Modern databases offer concurrent index creation:

Postgres: CREATE INDEX CONCURRENTLY. Slower but doesn't block writes.
MySQL: ALGORITHM=INPLACE for online index changes (recent versions).
For very large tables, sometimes you build the index on a replica, swap, etc.

Step 12: Edge Cases and Pitfalls

NULL Handling

Different databases handle NULL in indexes differently. Some skip NULL values entirely. Some require explicit NULL handling. Know your database's behavior or your WHERE col IS NULL query may not use the index.

Function Calls in WHERE

WHERE LOWER(email) = '[email protected]' cannot use a regular index on email. The function transforms the value at query time.

Fix: index the expression itself. CREATE INDEX idx_lower_email ON users (LOWER(email)); Postgres and others support functional indexes.

Implicit Type Conversion

WHERE id = '42' when id is INT can disable the index. The database might convert every id to string for comparison rather than convert '42' to int once.

Always pass values in the correct type.

OR Clauses

WHERE col1 = 'a' OR col2 = 'b' sometimes fails to use either index because the optimizer thinks both possibilities need full evaluation. Some databases rewrite to UNION; some don't.

If common, consider rewriting as a UNION manually.

Cardinality Mismatches

Index on a column where 99% of rows have the same value is nearly useless. The optimizer often correctly skips it for the 99% case (where a seq scan is faster) but uses it correctly for the rare 1% case. Monitor query plans.

Stale Statistics

The query planner uses statistics about column distributions. After bulk loads, statistics may be stale. Run ANALYZE (Postgres) or ANALYZE TABLE (MySQL) to update them.

Locking and Index Maintenance

Heavy write workloads on indexed columns can cause lock contention. Some databases offer different lock granularities (row-level, page-level). For very high write rates, choosing fewer indexes or different storage engines (LSM) might be necessary.

Step 13: Index Strategy in Practice

Start With Required Indexes

Primary keys are always indexed (automatic). Foreign keys should usually be indexed (for join performance). Unique constraints create indexes automatically.

Add Indexes Driven By Slow Queries

Don't pre-emptively index. Run the application. Find slow queries (via slow query log, APM tools). For each, EXPLAIN it. Add indexes that help.

Composite Indexes for Common Filter Patterns

If queries consistently filter on (a, b, c), an index on (a, b, c) often beats three separate indexes.

Drop Unused Indexes

Periodically check index usage. Drop indexes nobody uses. Reduces write cost and frees memory.

Don't Index Tiny Tables

For tables under a few thousand rows, full scans are often faster than indexes. The query planner usually figures this out, but you don't need to add an index just because.

Cover Hot Read Paths

For the absolute hottest queries (homepage feeds, login, checkout), consider covering indexes. Trade storage for speed.

Step 14: Recap of Key Decisions

B-tree is the right default. Handles the most common patterns: equality, range, ordering, prefix.
LSM-tree for write-heavy workloads. Cassandra, RocksDB, ScyllaDB.
Specialized indexes for specialized queries. Inverted for full-text, R-tree for spatial, GIN/GiST for JSON/arrays.
Composite indexes follow the leftmost prefix rule. Order matters.
Covering indexes for the hottest reads. Trade storage for speed.
Indexes are not free. Storage, write latency, memory pressure, maintenance.
Use EXPLAIN to verify. Don't assume; check.
Drop unused indexes periodically. They accumulate cruft over time.

The One Thing to Remember

An index is a deal: you pay write time, storage, and memory in exchange for read time. Made wisely (one or two indexes on the columns you actually query), indexes are the difference between a database that scales and one that crawls. Made carelessly (an index on every column), they slow writes to a halt without helping reads. The skill is recognizing which queries are slow, what kind of access they need, and what index would make them fast. Always verify with EXPLAIN before assuming an index helps. Always check usage statistics before keeping an index. The single most expensive mistake in database tuning is adding an index that nobody uses; the second is not adding one that everyone needs.