Skip to content

database index

A database index is a separate data structure that a database maintains alongside a table so it can locate the rows matching a column value without reading every row in the table.

Without an index, a query that filters on a column has to perform a full table scan, checking each row in turn, which takes O(n) time for n rows. An index stores the indexed column’s values in an organized form, each paired with a pointer to the row that holds it. The database searches that structure first and then jumps straight to the matching rows.

Most relational databases build indexes as B-trees, or close variants like the B+ tree, by default. A B-tree keeps its keys in sorted order across wide, shallow nodes, so a lookup touches only a handful of disk pages and runs in O(log n) time, much like a binary search tree built for disk. Sorted order also lets the same index serve range conditions, prefix matches, and sorted output.

In the widget below, pick a customer_id and run both lookups to see how many rows a full table scan reads compared with the two index pages and single row that a B-tree lookup touches:

Interactive diagram — enable JavaScript to view.

Other index types trade that flexibility for speed or size on specific workloads:

  • Hash index: Maps each key through a hash function, as a hash table does, giving fast equality lookups but no support for ranges or sorting.
  • Composite index: Covers several columns at once and helps queries that filter on its leading columns, the ones listed first in the index definition.
  • Unique index: Rejects duplicate values, which is how many databases enforce primary key and unique constraints.
  • Full-text index: Maps the words in a text column to the rows that contain them, an inverted index that powers keyword search.

Indexes aren’t free. Each one takes extra storage, and every insert, update, or delete on the table has to update the index too, which slows writes. A SQL query planner decides on each request whether an index is worth using, and it often skips one when a filter matches a large share of the table.

How to Create an Index in Django Without Downtime

Tutorial

How to Create an Index in Django Without Downtime

In this step-by-step Python tutorial, you'll get a solid understanding of the limitations of Django migrations by tackling a well known problem: creating an index in Django with no downtime.

advanced databases django

For additional information on related topics, take a look at the following resources:

Have a question about this? Mentor AI can show you examples, compare related terms, and point you to tutorials.


By Martin Breuss • Updated Nov. 4, 2026