B-Tree Indexing

1. What Is It?

A B-Tree (Balanced Tree) index is a separate data structure the database maintains alongside a table to make lookups, range scans, and sorts faster. Without an index, a query like WHERE email = 'alice@example.com' must scan every row in the table to find matches — O(n). With a B-Tree index on email, it navigates the tree to find the match in O(log n) and fetches only the relevant rows.

B-Tree is the default index type in PostgreSQL, MySQL, SQLite, and SQL Server. When you write CREATE INDEX, you're creating a B-Tree unless you specify otherwise. Understanding how it works lets you predict when queries will use an index and when they won't.

2. How It Works

A B-Tree index is a balanced tree of sorted keys. Each leaf node contains index key values and pointers to the actual table rows (heap pointers). Internal nodes contain separator keys that guide traversal.

                        [50]
                       /     \
              [20, 35]         [70, 85]
             /   |   \         /   |  \
         [1-19][21-34][36-49][51-69][71-84][86-99]
          ↕       ↕       ↕       ↕       ↕      ↕
        heap    heap    heap    heap    heap    heap
        rows    rows    rows    rows    rows    rows

Lookup (point query WHERE id = 42):

1. Start at the root
2. Compare 42 to each separator key, descend to the appropriate child
3. Reach a leaf node, find the key, follow the heap pointer
4. Read the table row

Depth of a B-Tree on a table with millions of rows is typically 3–5 levels — the tree stays shallow because each node holds many keys.

Range scan (WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31'):

1. Navigate to the first matching leaf (2024-01-01)
2. Scan leaf nodes sequentially (leaf nodes are linked) until past 2024-01-31
3. For each leaf entry, fetch the heap row

Covering index (index-only scan): If all columns in the query appear in the index, the database can return results from the index without touching the table at all. This eliminates the heap I/O:

Copy
-- Index on (user_id, placed_at, total_cents)
SELECT placed_at, total_cents FROM orders WHERE user_id = 123;
-- If the index covers all selected columns, no heap access needed

How the index is maintained: Every INSERT, UPDATE, or DELETE on the indexed table also updates the B-Tree. This is the write overhead of indexes.

3. What SDEs Actually Need to Know

Queries that use a B-Tree index:

• WHERE col = value — equality lookup
• WHERE col > value — range scan (also <, >=, <=, BETWEEN)
• ORDER BY col — index provides pre-sorted order, may eliminate a sort step
• WHERE col IN (v1, v2, v3) — multiple point lookups
• WHERE col LIKE 'prefix%' — prefix match (the index IS used for prefix patterns)
• WHERE col IS NULL — B-Tree indexes in PostgreSQL and MySQL (InnoDB) do store NULL values, so IS NULL can use a B-Tree index

Queries that do NOT use a B-Tree index:

• WHERE LOWER(col) = 'alice' — function on the column breaks index use; create a functional index instead
• WHERE col LIKE '%suffix' — leading wildcard; can't seek in a B-Tree
• WHERE col != value — inequality predicates typically force a full scan

Index column order matters for composite indexes. A composite index on (user_id, status, placed_at) is useful for:

• Queries filtering on user_id alone
• Queries filtering on user_id AND status
• Queries filtering on user_id AND status AND placed_at

It is NOT useful for queries filtering on status alone or placed_at alone — because the tree is sorted by user_id first, and without constraining user_id, the entire index must be scanned.

The leading column rule: A composite index is only usable starting from the leftmost column. Skipping a column breaks the ability to seek into the tree.

Use EXPLAIN to verify index usage:

Copy
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, total_cents FROM orders WHERE user_id = 42 AND status = 'paid';

Key things to look for:

• Index Scan or Index Only Scan — index is being used
• Seq Scan — full table scan, no index used
• rows= estimate vs. actual rows — large discrepancy means stale statistics (run ANALYZE)

4. Tradeoffs & Decisions

More indexes = faster reads, slower writes

Each index is a separate structure that must be updated on every write. A table with 10 indexes on it has 10 update operations per INSERT/UPDATE/DELETE. For write-heavy tables (logs, events, time-series), too many indexes degrades write throughput significantly.

Guideline: index columns you filter or sort on in frequent queries; avoid indexing columns that are rarely queried.

Index size and storage

Indexes consume disk space. A B-Tree index on a large TEXT column can be as large as the table itself. For large text values, consider prefix indexes or full-text search indexes (GIN/GiST) instead.

When does the optimizer skip a small-table index?

The query planner estimates that a sequential scan is cheaper when the table is small enough to fit in a few disk pages. On a 500-row table, a Seq Scan is often faster than an Index Scan because the index adds overhead. Don't panic if EXPLAIN shows a Seq Scan on a tiny table.

High-cardinality vs. low-cardinality columns

B-Tree indexes are most effective on high-cardinality columns (many distinct values — e.g., email, user_id). On low-cardinality columns (e.g., a status column with 3 possible values), an index scan often reads a large fraction of the table anyway, and the planner may choose a sequential scan. For low-cardinality filtering, partial indexes or composite indexes that include a high-cardinality leading column are better.

Partial index: Index only a subset of rows:

Copy
-- Index only active users — smaller index, faster lookup when filtering active users
CREATE INDEX idx_users_active_email ON users(email) WHERE deleted_at IS NULL;

5. Interview Cheat Sheet

Key sentences:

• "A B-Tree index is a sorted, balanced tree structure that reduces lookups from O(n) sequential scan to O(log n) tree traversal."
• "Composite indexes are useful from the leftmost column — skipping a leading column breaks the ability to seek into the index."
• "Every index speeds up reads but slows down writes — index columns you query often, not every column."
• "Applying a function to an indexed column in a WHERE clause breaks index use: WHERE LOWER(email) = ? doesn't use the email index."

Common follow-ups:

Q: What is an index-only scan and when does it happen? A: An index-only scan returns results from the index without touching the table (heap). It happens when all columns referenced in the query — both SELECT and WHERE — are present in the index. It's faster than a regular index scan because it skips the heap I/O. In PostgreSQL, the visibility map must also show the pages as all-visible for a true index-only scan.

Q: How do you decide what to index? A: Look at slow queries (via slow query log or pg_stat_statements), identify the filter/sort columns, check whether an index exists on those columns (EXPLAIN), and create targeted indexes. Avoid creating indexes preemptively on columns that aren't in real query predicates.

Q: What is index bloat and how does it happen? A: B-Tree pages accumulate dead entries from deleted or updated rows. In PostgreSQL, these are reclaimed by VACUUM. If VACUUM doesn't run frequently enough (or is blocked), the index grows larger than necessary, degrading performance. You can rebuild an index with REINDEX CONCURRENTLY to reclaim space without locking the table.