B-tree index

What a B-tree index is

A B-tree (short for balanced tree) is a self-balancing tree data structure that maintains sorted data and allows searches, insertions, and deletions in logarithmic time. It is not glamorous. It does not appear on conference talk titles. It simply works, every time, without complaint. In PostgreSQL's implementation, the tree has three levels of pages:

• Root page — the single top-level page that points to internal pages
• Internal pages — intermediate pages that narrow the search range by directing traversal left or right
• Leaf pages — the bottom level, which stores the actual indexed values along with pointers (TIDs) to the corresponding table rows

Leaf pages are linked together in a doubly-linked list, which allows PostgreSQL to scan a range of values by walking the leaf chain rather than re-traversing from the root for each value. This is what makes range queries and sorted output efficient.

Because the tree is balanced, every lookup traverses the same number of levels regardless of the value being searched. For a table with a million rows, a B-tree index typically has 3-4 levels — meaning any value can be found in 3-4 page reads. This is O(log n) in practice, and it scales gracefully. A billion-row table might add one or two more levels. The B-tree does not panic as the household grows.

When to use B-tree indexes

B-tree indexes handle the most common query patterns in PostgreSQL — the bread and butter of daily household operations. They support:

-- Equality
SELECT * FROM users WHERE email = 'alice@example.com';

-- Range
SELECT * FROM orders WHERE created_at BETWEEN '2026-01-01' AND '2026-03-01';

-- Sorting
SELECT * FROM products ORDER BY price ASC LIMIT 20;

-- Prefix matching (anchored LIKE)
SELECT * FROM customers WHERE last_name LIKE 'Gib%';

-- JOIN conditions
SELECT o.* FROM orders o JOIN customers c ON o.customer_id = c.id;

• Equality (=) — finding a specific value is one tree traversal
• Range (<, >, <=, >=, BETWEEN) — locate the start of the range, then walk the leaf chain
• Sorting (ORDER BY) — the index is already sorted, so PostgreSQL can read it in order without a separate sort step
• Prefix matching (LIKE 'abc%') — treated as a range scan on the prefix
• JOIN conditions — the inner side of a nested loop join benefits from a B-tree on the join column
• MIN/MAX — a single traversal to the first or last leaf entry

If your query filters, sorts, or joins on a column with reasonable cardinality, a B-tree index is almost certainly the right choice. One does not hire a specialist when the house steward already knows the way.

Creating B-tree indexes

Because B-tree is the default index type, you do not need to specify USING btree — though you can for explicitness. I appreciate explicitness. It shows the next person reading your schema that you made a deliberate choice.

-- These two statements are equivalent — B-tree is the default
CREATE INDEX idx_orders_customer_id ON orders (customer_id);
CREATE INDEX idx_orders_customer_id ON orders USING btree (customer_id);

-- With a specific sort order
CREATE INDEX idx_orders_created_desc ON orders (created_at DESC NULLS LAST);

The DESC NULLS LAST variant is useful when your queries sort in descending order. PostgreSQL can scan a B-tree in either direction, but specifying the sort order in the index avoids a reverse scan in multicolumn indexes where columns sort in different directions.

To verify the index was created and is being used — and one should always verify:

-- Check which indexes exist on a table
SELECT indexname, indexdef
FROM pg_indexes
WHERE tablename = 'orders';

-- Check if a query uses your index
EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;
-- Look for "Index Scan using idx_orders_customer_id" in the output

Multicolumn B-tree indexes

A B-tree index can include multiple columns. The data is sorted by the first column, then by the second within each group of equal first-column values, and so on — like a household directory organized by department, then by seniority within each department.

-- Multicolumn B-tree index
CREATE INDEX idx_orders_status_created ON orders (status, created_at);

-- This index supports:
--   WHERE status = 'shipped'                          ✓ (uses first column)
--   WHERE status = 'shipped' AND created_at > '2026-01-01'  ✓ (uses both)
--   WHERE status = 'shipped' ORDER BY created_at      ✓ (filter + sort)

-- This index does NOT efficiently support:
--   WHERE created_at > '2026-01-01'                   ✗ (skips first column)

The critical rule is the leftmost prefix rule: a multicolumn index can be used for queries that filter on the first column, the first two columns, the first three, and so on — but not for queries that skip the leading column. An index on (status, created_at) helps queries that filter on status alone, but not queries that filter on created_at alone.

Column order matters. I cannot stress this sufficiently. Put the most selective equality column first, and the range or sort column last. This gives the planner the most flexibility and the tightest scan range. Getting the column order wrong is the indexing equivalent of organizing the wine cellar by bottle shape.

B-tree limitations

The B-tree is dependable, not omniscient. It works on sortable, scalar data. It does not help — or cannot be used — in the following cases:

• Array containment (@>) — use a GIN index instead
• JSONB containment and path queries — use a GIN index with jsonb_ops or jsonb_path_ops
• Full-text search (@@) — use a GIN index on a tsvector column
• Geometric and spatial queries — use a GiST index (or PostGIS)
• LIKE with a leading wildcard (LIKE '%foo') — no index type handles this well; consider a trigram GIN index (pg_trgm)
• Very low cardinality columns — a boolean column with 50/50 distribution gains little from a B-tree index because the planner will prefer a sequential scan anyway

When a B-tree is not the right fit, PostgreSQL offers GIN, GiST, BRIN, and hash indexes, each designed for different data shapes and query patterns. A well-run household employs specialists for specialist tasks — the B-tree need not feel slighted.

How Gold Lapel relates

Gold Lapel sits between your application and PostgreSQL as a query proxy, analyzing every query that passes through. When it detects queries that would benefit from a B-tree index — repeated equality or range filters on unindexed columns, joins hitting sequential scans, ORDER BY clauses triggering in-memory sorts — it recommends the index automatically. You need not audit every query yourself; that is precisely what staff are for.

Gold Lapel accounts for the trade-offs: it considers write frequency on the table, existing indexes that partially overlap, and the selectivity of the column before recommending a new index. The goal is not to index everything — a household with more staff than rooms is no household at all — but to identify the indexes that would make the most difference for your actual workload.