Short answers to what readers ask most about this topic.
How database indexes work and why B-trees dominate: page-fanout arithmetic, real Postgres EXPLAIN output, composite column order and the write cost of every index.
Matthews Wong
Software Engineer
Key Takeaway
A database index is a separate sorted structure, usually a B-tree, that finds rows by key in a few page reads instead of scanning the whole table. B-trees dominate because wide pages keep the tree shallow, sorted leaves serve ranges and ORDER BY, and every extra index adds write cost.
Most slow list screens in an ERP or POS system come down to one question: is the database reading the whole table to find twenty rows? A page that filters orders by customer and status, newest first, is fast with a thousand rows and painful with a million, and the fix is usually one index.
This post explains what that index is, why almost every relational database builds it as a B-tree, and where it stops helping. The numbers come from two places: the PostgreSQL documentation, and a throwaway 1,000,000-row table I built on PostgreSQL 16.15 for this article. Every figure is either quoted from a source, derived with the arithmetic shown, or read from that one local run. They are not production benchmarks.
An index is a second copy of some columns, kept in sorted order, with a pointer back to the row. Without it, finding one customer means reading every page of the table. With it, the database walks a short path through the sorted copy and then fetches the single matching row. The test table below is 8,334 pages, and the same primary-key lookup touched 7 buffers.
-- The test table: 1,000,000 rows, PostgreSQL 16.15 on a laptop.
CREATE TABLE orders (
id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
customer_id int NOT NULL, -- 10,000 distinct customers
status text NOT NULL, -- paid / pending / void
created_at timestamptz NOT NULL,
total numeric(12,2) NOT NULL
);
-- Same lookup, before and after the primary key is used:
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT * FROM orders WHERE id = 777777;
-- Index Scan using orders_pkey on orders (actual rows=1 loops=1)
-- Index Cond: (id = 777777)
-- Buffers: shared hit=7
-- Table is 8,334 pages (a parallel seq scan reported hit=8334 in total).
-- Reading all of them to find one row: 8,334 / 7 = about 1,190 times more pages.The index is not free to keep. It takes disk space, it has to be updated by every write, and the planner will still ignore it when a query returns a large share of the table. Everything after this section is about that trade: what the structure looks like, how to confirm it is used, and what it costs.
Postgres stores every table and index as an array of fixed-size pages, usually 8 kB. A B-tree index is a tree of those pages: leaf pages hold the sorted keys with pointers to table rows, and internal pages hold keys that route a search to the right child. The original design is from Bayer and McCreight in 1972, and its abstract states lookups, insertions and deletions in time proportional to log base k of the index size, with at least 50 percent storage utilisation.
-- Fanout, worked by hand for a bigint primary key (assumptions marked).
page size = 8192 bytes (Postgres default)
bytes per index entry = 8 key + 8 tuple header + 4 item pointer
= 20 bytes (assumption)
default leaf fillfactor = 90% (CREATE INDEX docs)
entries per leaf page = 8192 * 0.90 / 20 = about 368
leaf pages for 1,000,000 = 1,000,000 / 368 = about 2,717
size on disk = 2,717 * 8 KB = about 21.2 MB
measured orders_pkey = 21 MB (pg_relation_size)
internal level = 2,717 pages / ~400 children each = about 7 pages
root = 1 page pointing at those 7
-- bt_metap('orders_pkey') reported level = 2:
-- root -> internal -> leaf, three pages on every lookup path.
-- Growth: each extra level multiplies capacity by the fanout.
-- level 1 (root + leaves): ~400 * 368 = about 147,000 rows
-- level 2 (root, internal, leaves): ~400^2 * 368 = about 59 million rows
-- level 3 (one more internal layer): ~400^3 * 368 = about 23 billion rowsThe consequence is that tree height barely moves while the table grows by orders of magnitude. For a bigint key I assumed 20 bytes per entry, which is an estimate and not a quoted figure, and the result predicted the measured 21 MB primary key within about half a megabyte. A third level carries roughly 59 million rows. This is why adding an index to a ten-million-row table does not make lookups ten times slower than on a million rows.
Three properties of the structure line up with what applications actually ask of a database. A binary tree over 1,000,000 keys is about 20 levels deep, because log base 2 of 1,000,000 is roughly 19.9, and each level can be a separate page read. A B-tree packs hundreds of keys into one page, so the same data needs three.
| B-tree property | Consequence | Query it serves |
|---|---|---|
| Hundreds of entries per 8 kB page | Three pages deep for 1,000,000 rows | Point lookups: WHERE id = 777777 |
| Keys stay sorted across the leaf level | A scan walks neighbouring entries, no re-search | Ranges, BETWEEN, ORDER BY with LIMIT |
| Balanced: all leaves at the same depth | Lookup cost stays predictable as data grows | Tables that only ever grow, such as orders and ledgers |
| Full pages split instead of rewriting the tree | Inserts stay local, but cost extra writes | Steady write traffic, with the price shown later |
Sorted leaves are the part people underrate. An index that can only answer equality cannot return the newest twenty orders without reading and sorting them. A B-tree can walk to the end of the right key range and read backwards, which is the plan shown in the next section. I am not covering hash, GIN or BRIN indexes here; they exist for other query shapes, and this post only claims what the B-tree does.
Run EXPLAIN with ANALYZE and BUFFERS, and compare the pages touched rather than the milliseconds, because pages are stable between runs and timings are not. The three plans below are the same query against the same 1,000,000 rows. Only the index changed.
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT * FROM orders
WHERE customer_id = 4242 AND status = 'paid'
ORDER BY created_at DESC LIMIT 20;
-- 1) No index on customer_id yet:
-- Parallel Seq Scan on orders
-- Filter: ((customer_id = 4242) AND (status = 'paid'))
-- Rows Removed by Filter: 333316 (per worker)
-- Buffers: shared hit=8334
-- + Sort (top of the plan) total hit=8448
-- 2) CREATE INDEX orders_customer_idx ON orders (customer_id);
-- Sort Method: top-N heapsort
-- -> Bitmap Heap Scan on orders (Heap Blocks: exact=129)
-- Filter: (status = 'paid') Rows Removed by Filter: 77
-- -> Bitmap Index Scan on orders_customer_idx
-- total Buffers: shared hit=129 read=3 (132 pages)
-- 3) CREATE INDEX ... ON orders (customer_id, status, created_at);
-- Limit
-- -> Index Scan Backward using orders_cust_status_created_idx
-- Index Cond: ((customer_id = 4242) AND (status = 'paid'))
-- total Buffers: shared hit=20 read=3 (23 pages, no Sort node)Going from 8,448 pages to 132 was one single-column index. Going to 23 pages and removing the Sort node needed the composite index in the next section. Timings on a laptop would be noise here, so I am quoting buffer counts only.
| What the plan shows | What it means | What to try |
|---|---|---|
| Seq Scan with a large Rows Removed by Filter | No index matched the filter, so every page was read | Index the filtered column, if the query returns few rows |
| Bitmap Heap Scan, then a Sort node | The index found the rows but cannot deliver them in order | Extend the index so the sort column comes last |
| Index Scan or Index Scan Backward, no Sort | The index delivers rows already in the requested order | Nothing. This is the target shape |
A Seq Scan is not always a bug. When a query returns a large share of the table, reading it in order is cheaper than jumping through an index. In my run, status = 'paid' matches one third of the rows and the plan was a sequential scan, correctly.
Yes, and it is the mistake that wastes the most indexes. The PostgreSQL documentation states the rule: equality constraints on leading columns, plus any inequality on the first column without an equality, limit the portion of the index scanned. Conditions on columns further right are only checked inside the index. So put the columns you compare with equals first, and the range or sort column last.
-- Right: equality columns first, the sort/range column last.
CREATE INDEX orders_cust_status_created_idx
ON orders (customer_id, status, created_at);
-- Served by it: WHERE customer_id = ?
-- WHERE customer_id = ? AND status = ?
-- WHERE customer_id = ? AND status = ? ORDER BY created_at DESC
-- Not narrowed by it: WHERE status = ? AND created_at < ? (no customer_id)
-- Measured on PostgreSQL 16.15, 1M rows, for that last query:
-- Parallel Seq Scan on orders, Buffers: shared hit=8334
-- The index was ignored. Docs for current Postgres (18) describe a skip scan
-- that can help when the leading column has very few distinct values;
-- customer_id has 10,000, so do not count on it.
-- Size: single-column index 6,960 kB vs three-column index 39 MB,
-- about 5.7 times larger (39 MB = 39,936 kB; 39,936 / 6,960 = 5.7) for the same table.The index also has a cost proportional to its width. The three-column index was about 5.7 times larger than the single-column one, because each entry now carries three keys. Do not widen an index to cover every query. Widen it for the few queries that are hot, and leave the rest to the narrower indexes you already have.
For a list screen filtered by one owner and one status and sorted by newest, the pattern is (owner_id, status, created_at). I use it as a starting hypothesis for tenant-scoped ERP tables, then confirm it with EXPLAIN on a copy of real data before keeping it.
Every INSERT must add an entry to every index on the table, and every one of those entries is also written to the write-ahead log. I measured it by inserting 100,000 rows into four otherwise identical tables and reading the WAL position before and after. The table shows bytes of WAL generated.
| Table setup (100,000 rows inserted) | WAL bytes written | Versus no index |
|---|---|---|
| No indexes | 9,628,240 | 1.00x |
| 1 index (customer_id) | 16,863,912 | 1.75x |
| 3 indexes | 31,044,280 | 3.22x |
| 4 indexes | 37,675,888 | 3.91x |
-- How the numbers were taken (one session per table, after CHECKPOINT):
SELECT pg_current_wal_lsn() AS before \gset
INSERT INTO w3
SELECT g, (random()*9999)::int + 1, 'paid', now() + g * interval '1 second', 1
FROM generate_series(1, 100000) g;
SELECT pg_wal_lsn_diff(pg_current_wal_lsn(), :'before') AS wal_bytes;
-- Ratios are plain division: 16,863,912 / 9,628,240 = 1.75
-- 31,044,280 / 9,628,240 = 3.22
-- 37,675,888 / 9,628,240 = 3.91
-- Updates: an UPDATE that touches no indexed column can be a HOT update
-- (needs free space on the same page) and adds no index entries.
SELECT n_tup_upd, n_tup_hot_upd FROM pg_stat_user_tables WHERE relname = 'orders';This is one local run, so treat the ratios as the shape of the cost and not a constant. Updates have a second rule. Per the PostgreSQL documentation, a heap-only tuple update avoids new index entries when the update changes no indexed column and there is free space on the same page. Indexing a column that changes often, such as a status or a last-seen timestamp, removes that shortcut for every update.
Do not index a column just because it appears in a WHERE clause somewhere. Each index you keep is paid for on every insert, and on every update that changes its columns, whether or not any query ever uses it.
Run these five checks in order. Most indexes that fail at step one or two should not be built at all.
On a single VPS running Postgres alongside the application, this discipline matters more than it does on a large cluster, because the same disk and the same WAL carry both the reads you are speeding up and the writes you are slowing down.
An index is a sorted copy that trades write cost for read speed, and the B-tree wins because its wide pages keep that copy three pages deep for a million rows. Put equality columns first and the sort column last, prove the gain with buffer counts in EXPLAIN, and treat every index as a standing charge on every insert.