B-tree / B+tree Index

TechniqueDatabase InternalsJuniorMidUpdated Nov 10, 2026

Balanced, fan-out heavy tree where leaves hold sorted keys (and in B+trees, are linked for range scans). Lookup, insert, delete in O(log n).

When to Use B-tree / B+tree Index

Default secondary index in nearly every relational database (Postgres, MySQL/InnoDB, SQL Server). Great for point lookups, equality, range, ORDER BY, and prefix matches.

In Practice

InnoDB clusters the primary key as a B+tree; secondary indexes store primary key as the row pointer. Postgres uses a B+tree (the btree access method) as the default index type.

Sketch

Pseudocode

-- Postgres: index on (status, created_at) supports
-- WHERE status = 'open' ORDER BY created_at LIMIT 50
CREATE INDEX idx_orders_status_created
  ON orders (status, created_at);

How B-tree / B+tree Index Comes Up in Interviews

Scenario

You need point lookups by email AND range queries by signup_date on the same table. Which index strategy?

Hash indexes give O(1) point lookups but cannot serve range scans or ORDER BY. B-trees handle both at O(log n), which is why they're the default in essentially every general-purpose RDBMS.

Bitmap indexes shine on low-cardinality columns in data warehouses, not on email. Composite B-trees follow the leftmost-prefix rule: (a, b) helps queries on a or (a, b), not on b alone.

Scenario

Login looks up a user by email in a 5-million-row users table, and EXPLAIN shows a sequential scan that takes 800 ms per login. An admin screen also lists users sorted by email. What should you add?

A B-tree index on email keeps the values sorted in a shallow tree, so the database finds one email in a few page reads, O(log n), without reading all 5 million rows. The same sorted order serves the admin screen's ORDER BY email. A materialized view stores a query's result, the WAL makes writes durable, and MVCC lets readers and writers work at the same time; none of them speeds up a lookup by email.

An index is a separate, sorted structure of one or more columns that points back to each row, like the index at the back of a book. CREATE INDEX ON users (email) adds one, and a primary key or UNIQUE constraint creates one automatically. Every insert, update, and delete must also update each index, so index the columns your queries filter, join, or sort on, and leave the rest alone.