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:
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.
Related Resources
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.
For additional information on related topics, take a look at the following resources:
- Introduction to Python SQL Libraries (Tutorial)
- Data Management With Python, SQLite, and SQLAlchemy (Tutorial)
- Python and MySQL Database: A Practical Introduction (Tutorial)
- MySQL Databases and Python (Course)
- How to Do a Binary Search in Python (Tutorial)
- Introduction to Python SQL Libraries (Quiz)
- SQLite and SQLAlchemy in Python: Move Your Data Beyond Flat Files (Course)
- Data Management With Python, SQLite, and SQLAlchemy (Quiz)
- Creating a Binary Search in Python (Course)
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