We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
System Design and AI Engineering, by Roni Das. 984 interactive lessons.
Start LearningFoundation · Database Fundamentals
A data structure that speeds up database lookups. Like the index at the back of a book that lets you jump to the right page instead of reading every page.
In short
A database index is a separate, sorted data structure that stores the values of one or more columns along with pointers to the matching rows, so the database can find those rows by jumping straight to them instead of scanning the whole table. It trades extra disk space and slower writes for much faster reads.
In short
A database index is a separate, sorted data structure that stores the values of one or more columns along with pointers to the matching rows, so the database can find those rows by jumping straight to them instead of scanning the whole table. It trades extra disk space and slower writes for much faster reads.
Learn it in the course
This page is the free part.
₹1,111 in India$25 everywhere elseonce, for the whole course
The System Design course covers Index across a run of lessons, not one page. These 4 alone are about 70 minutes of step-by-step reading, every one with a quiz.
The planner stopped using an index somewhere between 19.7 and 39.8 percent of the table. A query on the second column of a composite index took 37.269 ms against 0.054, and five indexes took the same inserts from 160 ms to 751.
When your database indexes rot and queries slow to a crawl, how to fix it without taking the system down.
What a forward index stores and how search engines use it with the inverted index for BM25 scoring. Also shows how Lucene and Elasticsearch store it.
The data structure powering every search engine, mapping words to the documents that contain them.
all part of
System Design Masterclass
770 lessons · about 287 hours · 18 free to read
₹1,111in India, by UPI
$25everywhere else, by PayPal
It is really nice and good Please join the course
You own this course
Continue with Database Indexingpay once,
yours for life
Picture a 1,000-page textbook. To find every mention of "caching" you could read all 1,000 pages, or you could flip to the index at the back, see "caching ... 212, 478, 690", and jump straight there. A database index works the same way. The table is the book, the index is the back-of-book listing, and the page numbers are pointers to where each row physically lives.
Without an index, a query like SELECT * FROM users WHERE email = 'a@b.com' forces a full table scan: the database reads every row and checks it. On a table with 10 million rows that means 10 million comparisons. With an index on email, the database walks a sorted structure and finds the matching row in roughly 23 steps instead. That is the difference between hundreds of milliseconds and under a millisecond.
An index is a separate copy of selected column data, kept in sorted order, with a pointer back to the full row. It is not the data itself, which is why you can add and drop indexes at any time without changing your actual records.
Most relational databases (PostgreSQL, MySQL/InnoDB, SQL Server, Oracle) build indexes as a B-tree, specifically a B+ tree. A B-tree keeps keys sorted and balanced so that the tree stays shallow even as it grows. A table with a billion rows still only needs about 4 to 5 levels of tree, so a lookup touches only a handful of disk pages. B-trees are good for equality (= 'x') and range queries (BETWEEN, >, <, ORDER BY) because the data is already sorted.
Some workloads use other index types. A hash index gives O(1) equality lookups but cannot do range queries. PostgreSQL offers GIN and GiST indexes for full-text search, JSON, and geospatial data. Many search and analytics systems use an inverted index, which maps each term to the list of documents that contain it.
Indexes can be single-column or composite (multiple columns). Order matters in a composite index: an index on (last_name, first_name) helps queries that filter by last_name, or by last_name and first_name together, but does not help a query that filters only by first_name. A covering index goes further by including every column the query needs, so the database answers the query from the index alone and never touches the table.
Add an index to columns you frequently filter, join, or sort on: foreign keys, email and username lookups, status columns used in dashboards, created_at for time-range queries. A primary key is automatically indexed. The payoff is largest on big tables with selective queries that return a small slice of rows.
Indexes are not free. Each one is a second structure the database must update on every INSERT, UPDATE, and DELETE, so writes get slower and storage grows. A table with ten indexes can take several times longer to write than the same table with one. Indexes that nobody uses are pure cost, so it is worth dropping them.
Indexes also stop helping in predictable cases. A low-cardinality column like a boolean is_active that is true for 90 percent of rows is a poor index target, because the database would still read most of the table. Functions on the column (WHERE LOWER(email) = ...) bypass a plain index unless you build a matching functional index. Always confirm an index is actually used by reading the query plan with EXPLAIN.
Suppose an e-commerce orders table has 50 million rows and a dashboard runs SELECT * FROM orders WHERE customer_id = 8123 ORDER BY created_at DESC LIMIT 20. With no index, every page load scans 50 million rows and the query takes seconds. After running CREATE INDEX idx_orders_customer_created ON orders (customer_id, created_at DESC), the database jumps to the customer_id section, where rows are already sorted by created_at, and returns the latest 20 in a couple of milliseconds.
This is exactly how Postgres and MySQL power production apps. The composite order matters: customer_id first narrows to one customer, then created_at gives the sort for free, so the LIMIT 20 reads only 20 index entries. Run EXPLAIN ANALYZE before and after and you can watch the plan switch from Seq Scan to Index Scan.
PostgreSQL
Uses B-tree indexes by default, plus GIN, GiST, BRIN, and hash indexes for full-text, JSON, geospatial, and append-only data.
MySQL (InnoDB)
Stores the table itself as a clustered B+ tree on the primary key, with secondary B-tree indexes pointing back to it.
MongoDB
Builds B-tree indexes on document fields and offers compound, text, and geospatial indexes; queries without one trigger a slow collection scan.
Elasticsearch
Built entirely around the inverted index, mapping each term to the documents that contain it for fast full-text search.
No. An index only speeds up reads that filter, join, or sort on the indexed columns, and only when those queries are selective. It makes writes slower and uses more disk, so an index nobody uses is pure overhead. Always verify with EXPLAIN that the planner actually uses it.
A clustered index determines the physical order of the rows on disk, so the table data is stored inside the index itself. There can be only one per table. A non-clustered (secondary) index is a separate structure that points back to the rows. In MySQL InnoDB the primary key is clustered; PostgreSQL does not cluster by default.
A composite index is sorted left to right, like a phone book sorted by last name then first name. You can find everyone named Smith, but you cannot efficiently find everyone named John without scanning, because the John entries are scattered. Put the column you filter on most, or most selectively, first.
There is no fixed number, but each index slows down INSERT, UPDATE, and DELETE and consumes storage. A common sign of too many is write performance dropping while some indexes are never read. Periodically check index usage statistics and drop ones the query planner never picks.
A covering index includes every column a query needs, either as key columns or included columns, so the database answers the query from the index alone without reading the table. This is called an index-only scan and is one of the biggest single wins for hot read paths.
Index Rebuilding
When your database indexes rot and queries slow to a crawl, how to fix it without taking the system down
Forward Index
What a forward index stores and how search engines use it with the inverted index for BM25 scoring. Also shows how Lucene and Elasticsearch store it.
Inverted Index
The data structure powering every search engine, mapping words to the documents that contain them
Bitmap Index
Bit arrays that make low-cardinality queries blazing fast, the secret weapon of data warehouses
Geospatial Indexing
How databases efficiently answer 'find everything near me'. R-trees, geohashes, and spatial queries
SQL
Structured Query Language for managing relational databases. Tables, rows, columns, and powerful joins to query related data.
Database
An organized collection of data that can be easily accessed, managed, and updated. The backbone of almost every application.
NoSQL
Databases that don't use traditional table-based relational models. Includes document stores, key-value, graph, and column-family databases.
ACID
Four guarantees for database transactions: Atomicity (all or nothing), Consistency (valid states only), Isolation (no interference), Durability (changes persist).
BASE
An alternative to ACID for distributed systems: Basically Available, Soft state, Eventually consistent. Trades strong consistency for availability.
Sharding
Splitting a database into smaller pieces (shards) distributed across multiple servers. Each shard holds a subset of the data.
This page explains the idea. The "Database Indexing" lesson builds it up step by step, with diagrams. It is part of the System Design Masterclass course, which has 770 lessons. 18 of them are free to read. You pay once and keep it for life, with no subscription.
Open the Database Indexing lessoncourse 1
From absolute beginner to principal engineer, drawn step by step.
Asked about Index in an interview?
Each question has why it is asked, a full answer, what the interviewer listens for, the follow-ups, the common mistakes and a diagram (268 diagrams in all). A PDF you keep, junior to staff level.
India: UPI, cards or netbanking through Razorpay. Elsewhere: card or PayPal. Download at once from My packs.
