If you've ever added an index to speed up a slow query, you've used a B-tree — whether you knew it or not. B-trees are the dominant index structure in relational databases, and for good reason: they handle equality and range queries efficiently, maintain sorted order, and degrade gracefully under write pressure. Understanding why B-trees win over alternatives is essential for making informed indexing decisions.
The B-Tree Structure
A B-tree is a self-balancing tree where each node can hold multiple keys and children. The key properties are:
- All leaves are at the same depth
- Each internal node has between
ceil(m/2)andmchildren (wheremis the order) - Keys within a node are sorted
- The tree stays balanced as elements are inserted and deleted
[30 | 60]
/ | \
[10|20] [40|50] [70|80]
/ | \ / | \ / | \
[..] [..] [..] [..] [..] [..] [..] [..] [..]The critical insight: with a branching factor of 500 (typical for 4KB pages), a 3-level B-tree can index 125 million rows. That's three disk reads to find any record in a table with hundreds of millions of rows.
B-Tree vs Hash Index
Hash indexes map keys directly to bucket positions using a hash function. They offer O(1) lookup for equality queries but cannot support range queries, prefix matching, or sorted iteration.
-- Hash index: only equality
CREATE INDEX idx_users_email_hash ON users USING hash (email);
SELECT * FROM users WHERE email = 'alice@example.com'; -- Fast O(1)
SELECT * FROM users WHERE email LIKE 'alice%'; -- Cannot use hash index
-- B-tree index: equality + range
CREATE INDEX idx_users_email_btree ON users USING btree (email);
SELECT * FROM users WHERE email = 'alice@example.com'; -- Fast O(log n)
SELECT * FROM users WHERE email LIKE 'alice%'; -- Range scan
SELECT * FROM users WHERE email BETWEEN 'a' AND 'm'; -- Range scanPostgreSQL didn't even have hash indexes in production until version 10. Before that, they weren't WAL-logged and couldn't survive crashes. B-trees were simply more reliable.
tradeoff / Lookup Speed vs Versatility
Hash indexes make sense for exact-match lookups in append-only workloads (like time-series data with exact timestamp lookups). B-trees win for anything that might need range scans or sorted output.
Hash indexes win on pure equality lookups but cannot support range queries. B-trees handle both with acceptable performance for most workloads.
Covering Indexes: Avoid the Table Lookup
A covering index includes all columns needed by a query, eliminating the need to visit the table heap. This is one of the most impactful optimizations you can make.
-- Standard index: requires heap lookup
CREATE INDEX idx_orders_customer ON orders (customer_id);
EXPLAIN ANALYZE SELECT customer_id, total FROM orders WHERE customer_id = 42;
-- Index Scan using idx_orders_customer on orders
-- Filter: (customer_id = 42)
-- Rows Removed by Filter: 0
-- -> Index Scan using idx_orders_customer on orders
-- Index Cond: (customer_id = 42)
-- -> Heap Fetches: 1000 <-- These are expensive
-- Covering index: no heap access needed
CREATE INDEX idx_orders_customer_covering ON orders (customer_id) INCLUDE (total);
EXPLAIN ANALYZE SELECT customer_id, total FROM orders WHERE customer_id = 42;
-- Index Only Scan using idx_orders_customer_covering on orders
-- Index Cond: (customer_id = 42)
-- -> Heap Fetches: 0 <-- No table access!The performance difference can be dramatic. With covering indexes, you avoid random I/O to the heap, which is often the bottleneck for read-heavy queries.
Index-Only Scans: When the Index Is the Table
PostgreSQL's planner will use index-only scans when all required columns are in the index. However, it still needs to verify that the visibility map indicates all tuples on the page are visible to all transactions.
-- Force index-only scan behavior
VACUUM orders; -- Updates the visibility map
EXPLAIN ANALYZE
SELECT customer_id, total, status
FROM orders
WHERE customer_id = 42;
-- Index Only Scan if all columns in index and visibility map is set
-- The visibility map is critical:
-- Without VACUUM, PostgreSQL must check the heap for visibility
-- This eliminates the benefit of index-only scansComposite Index Order
The order of columns in a composite index matters. B-tree indexes follow the leftmost prefix rule: the index can be used for queries that filter on the leftmost columns of the index.
-- Composite index on (status, created_at, customer_id)
CREATE INDEX idx_orders_composite ON orders (status, created_at, customer_id);
-- Can use the index:
SELECT * FROM orders WHERE status = 'pending';
SELECT * FROM orders WHERE status = 'pending' AND created_at > '2026-01-01';
SELECT * FROM orders WHERE status = 'pending' AND created_at > '2026-01-01' AND customer_id = 42;
-- Cannot use the index efficiently:
SELECT * FROM orders WHERE created_at > '2026-01-01'; -- Skips status
SELECT * FROM orders WHERE customer_id = 42; -- Skips status and created_atThe rule: put equality columns first, then range columns, then covering columns. This maximizes the index's ability to narrow the scan.
Index Maintenance Overhead
Every index must be updated when rows are inserted, updated, or deleted. This is the fundamental tradeoff: more indexes speed up reads but slow down writes.
-- Each index adds overhead to writes
CREATE INDEX idx_a ON t (a);
CREATE INDEX idx_b ON t (b);
CREATE INDEX idx_c ON t (c);
-- INSERT into t must update all three indexes
-- This means:
-- 1. Find the correct leaf page for each index
-- 2. Insert the key
-- 3. Split pages if full (cascading splits)
-- 4. Update the visibility map
-- 5. WAL log all changes// Simplified B-tree insertion (from PostgreSQL source)
// When a page splits, the tree must be rebalanced
static void _bt_insertonpg(Relation rel, Buffer buf, ...){
// Check if page has room
if (PageGetFreeSpace(page) < sizeof(ItemIdData) + MAXALIGN(size)){
// Page split required
Buffer newbuf = _bt_split(rel, buf, ...);
// Insert new key into parent
_bt_insertonpg(rel, newbuf, ...);
}
}Synthesis
B-trees win because they balance read performance, write overhead, and structural simplicity better than any alternative. They support equality and range queries, maintain sorted order, and degrade gracefully. The practical optimizations — covering indexes, index-only scans, and composite index ordering — amplify their effectiveness. Understanding these mechanics lets you design indexes that serve your query patterns without over-indexing.