Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 90 ยท Indexes

B-tree Indexes

Master the default PostgreSQL index: multicolumn order, equality then range, ASC/DESC and NULLS FIRST, unique indexes, INCLUDE columns and index-only scans.

When you write CREATE INDEX without naming a type, PostgreSQL builds a B-tree. It is the default for a reason: it handles equality, ranges, sorting, min and max, prefix matching on text, and uniqueness, which covers the large majority of real queries. The other index types you will meet later (GIN, GiST, BRIN and friends) are specialists for particular data. The B-tree is the generalist you reach for first.

A B-tree keeps its keys in sorted order in a balanced tree of 8 kB pages. Finding a key means walking from the root down to a leaf, which takes only three or four page reads even for a hundred million rows, and neighbouring keys sit next to each other, so a range is a short walk along the leaves. Almost every design decision in this lesson follows from one fact: the index is sorted, and a query can only exploit that sort order from the left. The PostgreSQL commands here are shown read-only, and the live SQLite examples use the same sorted-tree idea, so you can watch the planner reason about order in your browser. For the heap and TID background, see How Indexes Work in PostgreSQL.

Multicolumn indexes: equality first, then one range

A multicolumn index sorts by the first column, then by the second inside each first-column value, and so on, like a phone book sorted by last name and then first name. Consider an index on (customer_id, ordered_at):

SQL
CREATE INDEX orders_customer_date_idx ON orders (customer_id, ordered_at);

This index answers "customer 8, since March" extremely well: jump to customer 8, then jump to March inside that customer, then read forward. It answers "everyone since March" poorly, because the dates are only sorted within each customer, so matching entries are scattered across the whole index. The rule of thumb is:

  • Put columns compared with equality first.
  • Put the column with a range (>, <, BETWEEN) or the ORDER BY column after them.
  • A condition on a column after the first range column can still be checked against the index entries, but it no longer narrows where the scan starts and stops.

The same sort-from-the-left logic applies in SQLite, so you can check it live:

SQL Equality first, then range ยท database: shop

Press Run (or Ctrl + Enter) to see the result here.

Plans 1 and 2 show SEARCH ... (customer_id=? AND ordered_at>?), so the database seeks directly. Plan 3 says SCAN ... USING COVERING INDEX, reading all index entries because there is no leading column to seek on.

PostgreSQL behaves the same way up to one improvement. In PostgreSQL 18, a multicolumn B-tree can use a skip scan: when the leading column is missing from the condition, the planner can hop from one distinct leading value to the next and do a small search in each. It pays off when the leading column has few distinct values (say, a country column with 40 values). With millions of distinct leading values it is no better than reading the whole index, so design your index order as if skip scan did not exist, and treat it as a safety net. (PostgreSQL 17 and later also handle IN (...) lists on index columns more efficiently.)

Sort order and NULLs

A B-tree can be read forwards and backwards, so one index serves both ORDER BY ordered_at and ORDER BY ordered_at DESC. The direction only matters when you mix directions across several columns. An index on (status ASC, ordered_at DESC) matches ORDER BY status, ordered_at DESC and its exact opposite (read backwards), but it cannot satisfy ORDER BY status, ordered_at without an extra sort step.

SQL Mixed sort directions ยท database: shop

Press Run (or Ctrl + Enter) to see the result here.

The first two plans only say SCAN orders USING COVERING INDEX orders_status_date_idx. The third adds USE TEMP B-TREE FOR LAST TERM OF ORDER BY: the index fixes the order of status, but inside each status it has dates in the wrong direction, so the rows of each group must be re-sorted. In PostgreSQL the same situation shows up as a Sort node (or an Incremental Sort) above the scan.

NULLs have a position in the sort order, and here PostgreSQL and SQLite disagree, which catches people who test on one and deploy on the other:

  • PostgreSQL treats NULL as larger than any value: ASC puts NULLs last, and DESC puts them first.
  • SQLite treats NULL as smaller than any value, the opposite.

You can override the default per query and per index with NULLS FIRST or NULLS LAST. For PostgreSQL to use an index for a query that spells out the NULL position, the index must use the same one:

SQL
-- Newest first, rows with no date at the end
CREATE INDEX orders_shipped_idx ON orders (shipped_at DESC NULLS LAST);

SELECT id, shipped_at FROM orders ORDER BY shipped_at DESC NULLS LAST LIMIT 20;

The default for DESC is NULLS FIRST, so without the explicit clause in both places this "latest orders" query would list the unshipped ones first, or fail to use the index. SQLite accepts NULLS FIRST and NULLS LAST in ORDER BY but not in CREATE INDEX, so the index above is PostgreSQL-only. Here is the default ordering difference in action (compare with the PostgreSQL results written in the comments):

SQL Where do NULLs sort?

Press Run (or Ctrl + Enter) to see the result here.

In SQLite the first query lists Ines (no manager) first; PostgreSQL would list her last. The second query lists her last in both. Writing the NULL position explicitly in anything you share between engines is cheap insurance.

Unique indexes

CREATE UNIQUE INDEX and the UNIQUE and PRIMARY KEY constraints are all B-tree indexes underneath, because checking uniqueness needs a sorted lookup. Two details are specific to PostgreSQL:

  • NULLs are distinct by default: a unique index allows any number of rows with a NULL key, because NULL = NULL is not true. From PostgreSQL 15 you can write UNIQUE NULLS NOT DISTINCT to treat NULLs as equal, so at most one NULL row is allowed.
  • A unique index on (a, b) forbids duplicate pairs, not duplicate values of each column.

SQLite follows the standard behaviour for NULLs, which you can confirm. This example fails on purpose at the very end:

SQL Unique indexes and NULLs (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

The table accepts two NULL rows and one SPRING, and the last insert stops with UNIQUE constraint failed: coupons.code.

INCLUDE columns and index-only scans

Normally every index scan goes back to the heap to fetch the columns the query wants. An index-only scan skips that visit when the index already contains everything the query selects, which can make a query several times faster. Imagine you often run:

SQL
SELECT customer_id, status, shipping FROM orders WHERE customer_id = 8;

An index on (customer_id) finds the rows but must visit the heap for status and shipping. You could add them as extra key columns, but that makes the index larger and sorts by values you never search on. PostgreSQL 11 added a cleaner tool, INCLUDE:

SQL
CREATE INDEX orders_customer_covering_idx
  ON orders (customer_id)
  INCLUDE (status, shipping);

Included columns are stored in the index leaf entries but are not part of the sorted key: you cannot search or sort by them, they do not affect uniqueness (so UNIQUE (email) INCLUDE (name) still enforces unique emails only), and they let a query that selects them be answered from the index alone. A matching plan reads Index Only Scan using orders_customer_covering_idx.

There is one more requirement unique to PostgreSQL. Because of MVCC, index entries do not say whether a row is visible to your transaction. PostgreSQL consults the visibility map, a per-page bit that VACUUM sets when all rows on a page are visible to everyone. If the bit is not set, the scan still visits the heap and the plan shows Heap Fetches: N. A table that is updated constantly and rarely vacuumed gets little benefit from index-only scans; VACUUM, Autovacuum and Bloat explains how to keep the map fresh.

SQLite has no INCLUDE, but a covering index there is built by listing the extra columns in the key, and the plan tells you when it works:

SQL A covering index ยท database: shop

Press Run (or Ctrl + Enter) to see the result here.

The first plan says USING COVERING INDEX and the second only USING INDEX, because it also needs ordered_at from the table. Do not turn every index into a covering index: each extra column makes the index bigger and slower to update. Keep covering indexes for hot, narrow queries.

Designing a B-tree index

Equality first Columns compared with = go on the left.
Then range or sort One range column, or the ORDER BY column, comes next.
INCLUDE the rest Extra columns for index-only scans, not for searching.

Match your index to your most important queries, not to your columns.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. You usually run WHERE tenant_id = ? AND created_at >= ?. Which index fits best?

    Equality columns go first and the range column next, so the scan can seek to the tenant and then to the start date within it.
  2. 2. What does INCLUDE (status) add to an index on (customer_id)?

    Included columns are payload in the leaf entries. They are not sorted, searchable or part of uniqueness, but they can make the index covering.
  3. 3. In PostgreSQL, where do NULLs appear by default in ORDER BY col ASC?

    PostgreSQL treats NULL as larger than every value, so ASC puts NULLs last and DESC puts them first. SQLite does the opposite.
  4. 4. Why might an index-only scan still show a lot of heap fetches?

    PostgreSQL can skip the heap only for pages that the visibility map marks all-visible. Updates clear that mark until VACUUM sets it again.

Summary

  • A B-tree is the default index type: sorted keys in a balanced tree, good for equality, ranges, sorting, min/max and uniqueness.
  • Multicolumn indexes work from the left: equality columns first, then one range or sort column. PostgreSQL 18 skip scan helps only when the leading column has few distinct values.
  • One index can be read both ways, but mixed ASC/DESC across columns needs a matching index or an extra sort.
  • PostgreSQL sorts NULLs as largest (last on ASC); SQLite sorts them as smallest. Use NULLS FIRST/LAST to be explicit.
  • Unique indexes allow many NULLs unless you use NULLS NOT DISTINCT (PostgreSQL 15+).
  • INCLUDE columns enable index-only scans, which also depend on VACUUM keeping the visibility map current.

Next: Partial and Expression Indexes, where you index only the rows or the computed values you really query.