Database Indexes Explained: B-Trees, Composite Keys and Write Costs

Without an index, the database reads every row to answer even a tiny question. That is fine at a thousand rows and painful at millions, when the query runs many times a second. What follows is database indexes explained on one such table, with every number measured.

Picture a common setup. An online shop keeps an orders table with 20 lakh rows, and its My Orders page asks for one customer's orders in March. The setup is made up, but every number here comes from real runs on PostgreSQL 16.15 and SQLite 3.45.1.

With no index on the customer, PostgreSQL read all 17,000 pages of the table, about 133 MB, to return 3 rows. It checked and threw away nearly 20 lakh rows. On our test machine that took 88 to 132 ms per request.

After one well-chosen index, the same query touched 6 pages and finished in under 0.1 ms. The rest of this guide explains why, and what that index costs you on every write.

You need six words. Each is used in the same meaning for the rest of the guide.

A database index is a separate structure that keeps chosen column values in sorted order, each paired with its row address. Because the values are sorted, the database can find a value without looking at the rest.

The SQLite file format spells this out. Every index is its own B-tree, and its key is the indexed columns followed by the rowid. PostgreSQL is similar: each leaf entry in a B-tree index holds key values and points to a table row.

The index at the back of a textbook is a fair picture. The topic words are the keys, sorted alphabetically. The page numbers are the row addresses. You find a word, then turn to its pages.

Where the picture breaks: a book index is printed once, but a database index must change on every insert, update and delete. A book index is also one flat list, while a database index is a tree of pages.

A B-tree is a balanced tree of pages. One root page sits at the top, internal pages sit in the middle, and leaf pages at the bottom hold the sorted keys. Balanced means every leaf is the same distance from the root.

A lookup starts at the root and compares the wanted key with the boundaries stored there. That picks one child page. The search repeats one level down until it reaches a leaf, then follows the row address into the heap.

On a warm run, EXPLAIN with BUFFERS counted 4 pages for this lookup: 3 index pages and 1 heap page. We counted the tree itself with pageinspect, an extension that shows raw index pages to superusers.

The primary key had 1 root page, 19 internal pages and 5,465 leaf pages. That is 99.6 percent leaves, close to the docs' note that over 99 percent of pages are usually leaves.

The tree stays shallow because each internal page holds hundreds of pointers. Each level multiplies the reach by a few hundred. When a leaf fills, it splits in two; when the root itself splits, the tree gains one level.

Pages on each level, leaves included, are linked to their neighbours. A plain range query such as all of March finds the first match, then walks right along the leaves. It does not start again from the root for each row.

Ask the database for its plan. SQLite prints it with EXPLAIN QUERY PLAN, and PostgreSQL with EXPLAIN. Adding ANALYZE and BUFFERS in PostgreSQL runs the query and counts the pages it touched.

Check a plan in SQLite from Python

This script builds a 2 lakh row orders table in memory and prints the plan three times. It needs only Python, because the sqlite3 module ships with it.

import random
import sqlite3

db = sqlite3.connect(":memory:")
db.execute(
    "CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER, "
    "status TEXT, created_at TEXT, total INTEGER)"
)
rows = [
    (random.randint(1, 20000), "delivered",
     f"2026-09-{1 + n % 28:02d} 10:00", random.randint(100, 5000))
    for n in range(200000)
]
db.executemany(
    "INSERT INTO orders (customer_id, status, created_at, total) "
    "VALUES (?, ?, ?, ?)", rows
)

query = (
    "SELECT id, total FROM orders WHERE customer_id = 4821 "
    "AND created_at BETWEEN '2026-09-01' AND '2026-09-30 23:59' "
    "ORDER BY created_at"
)


def show_plan(label):
    print(label)
    for row in db.execute("EXPLAIN QUERY PLAN " + query):
        print("   ", row[3])


show_plan("No index:")
db.execute("CREATE INDEX idx_cust_created ON orders (customer_id, created_at)")
show_plan("Customer first, then date:")
db.execute("DROP INDEX idx_cust_created")
db.execute("CREATE INDEX idx_created_cust ON orders (created_at, customer_id)")
show_plan("Date first, then customer:")

Expect SCAN orders and USE TEMP B-TREE FOR ORDER BY first: a full scan plus a separate sort. With the customer-first index you should see SEARCH orders USING INDEX idx_cust_created, listing customer_id and both created_at bounds.

With the date-first index, the SEARCH line lists only the two created_at bounds. That small difference is the column-order lesson of the next part. SQLite warns that this output format may change between releases, so read it, do not parse it.

Check a plan in PostgreSQL

CREATE INDEX idx_cust_created ON orders (customer_id, created_at);

EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT id, total
FROM orders
WHERE customer_id = 4821
  AND created_at BETWEEN '2026-03-01 00:00' AND '2026-03-31 23:59:59.999999'
ORDER BY created_at;

On our 20 lakh row table, a second run printed these lines. We left out the Index Cond line, which repeats the WHERE clause. COSTS OFF hides the planner's cost estimates, so your first line should match ours apart from the times.

Index Scan using idx_cust_created on orders (actual time=0.008..0.011 rows=3 loops=1)
  Buffers: shared hit=6
Planning Time: 0.046 ms
Execution Time: 0.018 ms

Read three things. The node name says how the table was read. The Buffers line counts page accesses, 8 KB each, here 6. Execution Time is in milliseconds.

BETWEEN includes both ends, which is why the end is 23:59:59.999999 and not just 31 March. PostgreSQL timestamps stop at microseconds, so this covers the whole last day. Our tests ran in the UTC time zone, which decides how these literals are read. Also, EXPLAIN ANALYZE really runs the statement. For an UPDATE or DELETE, wrap it in BEGIN and ROLLBACK.

PostgreSQL 18, the current release as of 23 October 2026, includes BUFFERS automatically with ANALYZE. PostgreSQL 19 was at release candidate 1 on that date. On version 16, which we tested, you must ask for it.

A composite index, also called a multicolumn index, sorts entries by its first column, then by the second within each first value. Its sort key is a composite key, which is not the same as a composite primary key, a uniqueness rule. It is one sorted list, not one list per column. That order decides which queries it can narrow.

For an index on (customer_id, created_at), the leaves run in this kind of order: customer 4821 on 3 March, 4821 on 19 March, 4822 on 2 January. All of one customer's orders sit together, already in date order.

The leftmost-prefix rule

Without skip scan, covered below, a B-tree index can narrow a search only when the query constrains its leading columns. The PostgreSQL docs give the exact rule: equality on leading columns, plus a range on the first column without equality, limits the scanned part.

So an index on (customer_id, created_at) serves a filter on customer_id alone, and customer_id with a date range. A filter on created_at alone gets no starting point. PostgreSQL 16 chose a full Seq Scan for it.

SQLite 3.45.1 did something worth knowing. It printed SCAN orders USING COVERING INDEX. The query asked only for id and created_at, both stored in the index, so SQLite read every index entry instead of the table. The word SCAN tells you nothing was narrowed.

Equality columns first, the range column last

The naive first try is one index per column: one on customer_id, one on created_at. It works, but not well. In SQLite, the customer index found the customer's rows and then needed a separate sort by date.

The better fix is one composite index, but which order? We built both orders on the 20 lakh row table and ran the same March query for one customer.

Customer first touched 6 pages in under 0.1 ms. Date first touched 1,424 to 1,472 pages across runs and took 13 to 19 ms. Both plans said Index Scan, so only the Buffers line showed the gap.

What just happened? The rule is to put columns you match exactly before the column you filter by range. In a date-first index, all of March is one long run of about 3.8 lakh entries. Customer 4821's three orders are scattered inside it, so the database must read the whole run and check each entry.

A gap in the columns stops the narrowing

SQLite's optimizer docs state the rule plainly: leading columns need =, IN or IS, only the last used column may be a range, and there can be no gaps. We tested an index on (customer_id, status, created_at).

A query on customer and dates, with no status filter, used only customer_id. It also needed a separate sort. Adding status IN ('delivered', 'pending') let SQLite use all three columns.

Skip scan softens the rule in newer versions

Skip scan lets a database use an index whose first column has no condition, or only a range, by jumping from one first-column value to the next. It usually pays off only when the first column has few distinct values.

PostgreSQL 18, released on 25 September 2025, added skip scan for B-tree indexes. We could not run version 18 here, so that claim comes from the release notes and docs, not our tests. PostgreSQL 16 has no skip scan.

SQLite also has skip scan, used only after ANALYZE shows about 18 or more duplicates per leading value. Our index on (status, customer_id) gave SCAN orders before ANALYZE had seen it. After ANALYZE, the plan used the index with ANY(status) for the first column.

A covering index holds every column a query reads, so the database can answer from the index alone. That skips the second lookup into the table for every matching row.

SQLite's docs describe the saving as one fewer binary search per row, which can make many queries run twice as fast. Appending total to our index gave SEARCH orders USING COVERING INDEX. Asking for status as well dropped the word COVERING again.

In PostgreSQL, the INCLUDE clause adds payload columns that are stored in the index but never used for searching. An index on (customer_id, created_at) INCLUDE (total) gave an Index Only Scan for a query asking for created_at and total.

Why an index-only scan can still visit the table

PostgreSQL must also know that each row is visible to your transaction, and that information lives in the heap. A visibility map, one bit per heap page, records pages where every row is visible to everyone. VACUUM, PostgreSQL's cleanup command for old row versions, is what set those bits again in our test.

When the bit is set, the index answer is enough. When it is not, the heap page is read anyway. The plan counts those visits as Heap Fetches.

Right after VACUUM our query showed Heap Fetches: 0. We then updated 1 row in every 50 across the table, and the same query showed Heap Fetches: 3. After another VACUUM it went back to 0.

So covering indexes pay off most on tables that change slowly or get vacuumed often. The docs also warn against wide payload columns: they bloat the index, and a too-large entry makes inserts fail.

Selectivity is the share of rows a filter keeps. A filter that keeps 2 percent of rows is selective; one that keeps 90 percent is not. An index helps most when it lets the database skip most of the work: most rows, and ideally most pages.

Our orders table has a status column: 90 percent delivered, 8 percent cancelled, 2 percent pending. We indexed status, ran ANALYZE, and asked PostgreSQL 16 for the sum of totals per status.

On warm runs, for delivered, the planner ignored the index and chose a Seq Scan, taking 163 ms. Forcing the index made it slower, at 243 ms. For pending, it used a Bitmap Heap Scan at 31 ms, against 70 ms for a forced scan.

The surprise is in the page count. Pending rows are only 2 percent, yet they sat on 15,382 of the 17,000 heap pages. When matching rows are scattered, even a selective filter reads most of the table. The index still won, 31 ms against 70 ms, because it did not test the 98 percent of other rows and read pages in physical order.

SQLite 3.45.1 made the opposite mistake in our in-memory test. Its statistics row stored only an average of 66,667 rows per status value. It used the index even for delivered, which took 22 to 32 ms against 12 to 19 ms for a forced scan.

A partial index fits the rare value

A partial index stores entries only for rows that match its own WHERE clause. If the app only ever looks up pending orders, index just those rows.

We created an index on customer_id WHERE status = 'pending' in PostgreSQL. Inserting 1 lakh delivered rows left it at one 8 KB page. Inserting 1 lakh pending rows grew it to about 2.2 MB.

Every ordinary index on a table gets a new entry for every inserted row. So one INSERT turns into one table write plus one write per index. In PostgreSQL each of those page changes is also recorded in the write-ahead log (WAL), the file every change goes to first.

This is called write amplification: one logical change causing several physical writes. The PostgreSQL docs put it simply: indexes add overhead to data manipulation, so indexes seldom or never used should be removed.

We measured it in PostgreSQL 16.15. Inserting 2 lakh rows into a table with only a primary key wrote 32 MB of WAL. The same insert with four extra indexes wrote 88 MB, 2.8 times as much.

Time followed. Inserting 1 lakh rows took 188 to 211 ms with the primary key only, and 662 to 824 ms with four extra indexes. In an in-memory SQLite database, 2 lakh inserts took 144 to 163 ms without indexes and 912 to 1,097 ms with four.

Your numbers will differ by machine, but the direction should hold, because each index adds its own writes. The indexes also took space: 20 MB against 4.4 MB for the primary key alone, on a 13 MB table.

Building an index costs something too. A normal CREATE INDEX in PostgreSQL blocks writes, not reads, until it finishes. CREATE INDEX CONCURRENTLY avoids that, but scans the table twice and cannot run inside a transaction block, the statements between BEGIN and COMMIT.

If a concurrent build fails, it leaves an index marked INVALID. Queries ignore it, yet it still costs update overhead, so drop it and build again.

How HOT updates let PostgreSQL skip index work

A HOT update, short for heap-only tuple, writes the new row version on the same heap page and adds no index entries. PostgreSQL does this only when two things hold.

• The update changes no column used by any index on the table. BRIN indexes, a summarising type, are the only core exception.
• The heap page holding the old row has enough free space for the new version.

When an update is not HOT, every index on the table gets a new entry, even indexes whose columns did not change. The B-tree docs say this directly for an update that changes one indexed column.

Our test table had a primary key and a (customer_id, created_at) index, filled to 90 percent. Updating status on 10,000 rows gave 10,000 HOT updates, and the index size did not change.

Updating created_at on another 10,000 rows gave zero HOT updates, and the index grew by about 200 KB. On a table packed to 100 percent, the default, the status update gave zero HOT updates out of 10,000.

Then we added an index on status. The same kind of status update was no longer HOT at all. That is the hidden cost of indexing a column your app updates constantly.

To check your own table, compare n_tup_hot_upd with n_tup_upd. A low share of HOT updates on an update-heavy table points to an index on a busy column, or full pages.

SELECT relname, n_tup_upd, n_tup_hot_upd
FROM pg_stat_user_tables
WHERE relname = 'orders';

Lowering fillfactor, the share of each page filled on insert, leaves room for HOT updates. The table default is 100; we used 90 in the test.

Ask PostgreSQL how often each index was scanned, then check a few traps before dropping anything. The view pg_stat_user_indexes keeps an idx_scan counter per index.

SELECT indexrelname, idx_scan, last_idx_scan,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
WHERE relname = 'orders'
ORDER BY idx_scan;

On PostgreSQL 16.15 this view also has last_idx_scan, the time of the latest scan. An idx_scan of 0 makes an index a candidate, not a verdict.

1. 1

   List the candidates

   Run the query above and note every index with a low idx_scan and a large size.

2. 2

   Check how long the counters ran

   Counters reset after a crash, an immediate shutdown, a restore or a manual pg_stat_reset. A week of data can miss a monthly report.

3. 3

   Check every server

   Each server, including each replica, keeps its own counters. An index unused on the primary may serve read queries on a replica.

4. 4

   Keep constraint indexes

   A primary key or unique index enforces a rule even with idx_scan at 0. Our primary key showed 0 scans and was still needed.

5. 5

   Drop without blocking writes

   Use DROP INDEX CONCURRENTLY, which waits for conflicting transactions instead of locking the table. Save the CREATE INDEX statement first.

6. 6

   Watch query times

   After the drop, watch query times for a full business cycle. Rebuild with CREATE INDEX CONCURRENTLY if a query regresses.

DROP INDEX CONCURRENTLY takes one index at a time and cannot run in a transaction block. It cannot drop an index that backs a UNIQUE or PRIMARY KEY constraint.

SQLite's query planner docs add a cheap rule: never keep two indexes where one is a prefix of the other. An index on (customer_id) is redundant next to (customer_id, created_at), unless the shorter one enforces a unique rule.

Start from the access pattern, not the table. A strong answer names the query you are speeding up, the index that serves it, and what it costs on writes.

1. 1

   Name the hot query

   Say it out loud: one customer's orders in a date range, in date order, a few hundred times a second.

2. 2

   Pick the index from the query

   Equality columns first, then the range or sort column: (customer_id, created_at). Add INCLUDE columns only if the query is very hot.

3. 3

   Explain the lookup cost

   A B-tree lookup reads one page per level. Our 20 lakh row index had 3 levels, so a lookup reads a handful of pages.

4. 4

   State the write cost

   Every index adds work to every insert and to non-HOT updates. Four extra indexes cost us 2.8 times the WAL.

5. 5

   Say how you would verify it

   Run EXPLAIN with ANALYZE and BUFFERS before and after, and compare pages touched, not only time.

6. 6

   Mention upkeep

   Build and drop indexes concurrently, refresh statistics with ANALYZE, and review idx_scan for unused indexes.