How database indexing works, with Postgres examples

A database index is a separate, sorted data structure that maps column values to the rows that contain them, so the database can jump straight to matching rows instead of reading the whole table. In PostgreSQL the default index is a B-tree, which answers equality and range lookups and can return rows already in order. The price is extra disk space and slower writes, because every index has to be updated when rows change.

What an index is

Think of the index at the back of a textbook. To find "Fundamental Rights", you don't read all 900 pages; you look up the term in a sorted list and go to the pages it names. A database index does the same for a column: a sorted list of values, each pointing to where its rows sit in the table.

In PostgreSQL the table itself (the heap) stores rows in no particular order. Without a suitable index, finding one student's attempts in a table of 1.2 crore mock-test attempts means a sequential scan: read every page and test every row. With an index on student_id, the database walks the index to that student's entries and fetches only those rows.

The query planner decides whether to use an index. A sequential scan is sometimes the right choice, for small tables or when a query needs a large share of the rows, because reading pages in order is cheaper than jumping around. An index that the planner never picks costs you on every write and helps nothing.

B-tree indexes

A B-tree is a balanced tree of pages. The leaf pages hold the indexed values in sorted order, each with a pointer to a row, and are linked left to right. Pages above them hold separator values that route a search down to the right leaf.

That shape explains its speed. PostgreSQL pages are 8 kB, so each page holds a few hundred entries for a compact key such as an integer. Three levels of a few hundred entries each already cover tens of millions of keys, so finding one value takes a handful of page reads whether the table has a lakh rows or a crore. Because leaves are sorted and linked, a B-tree also serves ranges (score BETWEEN 60 AND 80) and ORDER BY without a separate sort.

According to PostgreSQL's index types documentation, B-trees support <, <=, =, >= and >, plus BETWEEN, IN, IS NULL and prefix patterns such as LIKE 'SSC%' (with the C locale or a pattern operator class). The other types serve special cases:

Reading EXPLAIN ANALYZE

EXPLAIN shows the plan the database will use; EXPLAIN ANALYZE runs the query and adds what actually happened. Take a student's recent attempts:

EXPLAIN ANALYZE
SELECT id, test_id, score, submitted_at
FROM test_attempts
WHERE student_id = 48213
ORDER BY submitted_at DESC
LIMIT 20;

Without a suitable index, the plan has this shape (simplified and illustrative; a table this size would usually also use parallel workers):

Limit (actual rows=20 loops=1)
  ->  Sort (actual rows=20 loops=1)
        Sort Key: submitted_at DESC
        ->  Seq Scan on test_attempts (actual rows=180 loops=1)
              Filter: (student_id = 48213)
              Rows Removed by Filter: 11999820

Reading 1.2 crore rows to keep 180 is the tell. After adding an index that matches both the filter and the order, the shape changes:

CREATE INDEX CONCURRENTLY test_attempts_student_recent_idx
    ON test_attempts (student_id, submitted_at DESC);

Limit (actual rows=20 loops=1)
  ->  Index Scan using test_attempts_student_recent_idx on test_attempts
        Index Cond: (student_id = 48213)

The index delivers that student's rows already in date order, so there is no Sort node, and the Limit stops after 20 rows. What to look for in any plan:

• Node types. Seq Scan reads the whole table. Index Scan follows an index and visits the table. Index Only Scan answers from the index alone. Bitmap Heap Scan collects matches from an index first, then reads the table pages in order.
  
  
• Estimated vs actual rows. The PostgreSQL EXPLAIN guide calls this the thing most worth checking. Large gaps usually mean stale statistics (run ANALYZE) or correlated columns the planner can't see.
  
  
• loops. Times and rows are per loop, so multiply by loops to get the total, especially inside nested loops.
  
  
• Buffers. Shared hits were found in memory and reads came from disk or the OS cache. Since PostgreSQL 18, EXPLAIN ANALYZE shows this automatically.
  
  

Remember that EXPLAIN ANALYZE really runs the statement. For an UPDATE or DELETE, wrap it in BEGIN and ROLLBACK.

Composite, partial and covering indexes

Composite indexes

A composite index covers several columns, and the order matters. PostgreSQL's multicolumn index documentation explains the rule: equality conditions on the leading columns, plus a range condition on the next one, narrow the part of the index that is scanned. An index on (student_id, submitted_at) serves "this student's attempts by date", but not "all attempts yesterday", because submitted_at isn't the leading column. PostgreSQL 18 added skip scan, which can use such an index when the leading column has only a few distinct values, but don't design around it. A practical rule: equality columns first, then the column you filter by range or sort by.

Partial indexes

A partial index covers only the rows matching a condition. During a live test, the hot query looks for in-progress attempts, a small fraction of the table:

CREATE INDEX CONCURRENTLY test_attempts_in_progress_idx
    ON test_attempts (test_id, started_at)
    WHERE status = 'in_progress';

The index stays tiny, and rows that are submitted drop out of it. The query must include the same condition (WHERE status = 'in_progress') for the planner to use it.

Covering indexes

If an index contains every column a query needs, PostgreSQL can answer with an index-only scan and skip the table. The INCLUDE clause adds such payload columns without making them part of the search key:

CREATE INDEX CONCURRENTLY test_attempts_top_scores_idx
    ON test_attempts (test_id, score DESC) INCLUDE (student_id);

Now "top 100 scores for test 42" can be read from the index alone. The catch: an index-only scan still has to confirm that rows are visible, which it can skip only for table pages that vacuum has marked all-visible. On a table taking constant writes, like attempts during a live test, expect many table visits anyway.

The cost of indexes

• Slower writes. Every INSERT adds an entry to every index. An UPDATE usually does too, unless PostgreSQL can make it a heap-only (HOT) update, which needs the update to leave all indexed columns unchanged and to fit on the same page.
  
  
• Space and memory. Indexes take disk space and compete with table data for shared_buffers and the OS cache.
  
  
• Bloat. Indexes on heavily updated tables grow with dead entries. REINDEX INDEX CONCURRENTLY rebuilds one without blocking writes.
  
  
• Unused indexes. They cost all of the above and help nothing. pg_stat_user_indexes shows how often each index has been scanned:
  
  

SELECT relname, indexrelname, idx_scan,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
ORDER BY idx_scan, pg_relation_size(indexrelid) DESC;

Check replicas too before dropping anything, since an index unused on the primary may serve reports on a replica. And watch foreign keys: PostgreSQL doesn't index the referencing column automatically, so deleting a course can scan the entire lessons table. Django does add an index to every ForeignKey by default, which covers most apps built with it.

Creating indexes on a live database

A plain CREATE INDEX blocks inserts, updates and deletes on the table until it finishes. Reads continue, but on a busy attempts table, minutes of blocked writes during a test is an outage. CREATE INDEX CONCURRENTLY avoids that:

• Writes continue while it builds. In exchange, it scans the table twice, waits for existing transactions that could use the index to finish, and takes noticeably longer. A long-running transaction can hold it up.
  
  
• It can't run inside a transaction block. In Django, use AddIndexConcurrently from django.contrib.postgres.operations in a migration marked atomic = False.
  
  
• Only one concurrent index build can run on a table at a time.
  
  
• If it fails, for example on a duplicate value in a unique index, it leaves an INVALID index that is ignored by queries but still updated on every write. Drop it and try again, or use REINDEX INDEX CONCURRENTLY.
  
  

Schedule index builds away from test windows and peak lecture hours, and watch for invalid indexes afterwards. Our guide to zero-downtime migrations covers the other schema changes that lock tables.

Indexes are one part of keeping the database fast. When the same expensive result is read over and over, precompute it with a materialized view. When reads outgrow one server, spread them across read replicas, and for the wider picture of a system under peak load, see handling 100,000 concurrent users.

Key takeaways

• An index is a sorted structure that points to rows, letting the database skip reading the whole table.
  
  
• B-trees cover equality, ranges and sorting; GIN, GiST and BRIN handle arrays and JSONB, geometry and huge append-only tables.
  
  
• Read EXPLAIN ANALYZE for Seq Scans that discard most rows and for estimates far from actual counts.
  
  
• Order composite index columns as equality first, then range or sort; use partial and covering indexes for hot queries.
  
  
• Every index slows writes, so drop unused ones, and build new ones with CREATE INDEX CONCURRENTLY on a live table.
  
  

Frequently asked questions

How do database indexes work?

An index keeps a sorted copy of one or more columns, with each entry pointing to its row in the table. Most databases use a B-tree, a shallow balanced tree of pages, so finding a value takes only a few page reads even in very large tables. The query planner compares the cost of using an index against reading the whole table, and picks whichever it estimates to be cheaper.

What is database indexing and why is it important?

Database indexing is creating these lookup structures on the columns your queries filter, join and sort by. It matters because it can turn a query that reads crores of rows into one that reads a handful of pages, which keeps the app responsive and stops the database collapsing under peak load. The trade-off is slower writes and extra storage, so index for real queries, not every column.

What is indexing databases?

Indexing a database means deciding which indexes to create and then creating them: finding slow or frequent queries, reading their plans with EXPLAIN ANALYZE, and adding indexes that match their filters and sort order. In PostgreSQL that is usually a B-tree, sometimes composite, partial or covering. On a live system, build them with CREATE INDEX CONCURRENTLY and review unused indexes regularly.