An index is a separate, ordered (or hashed) data structure that maps column values to the location of the rows holding them, so the database can jump to matching rows instead of reading the whole table. Interviewers probe it because "add an index" is the most common performance fix, and the follow-up questions reveal whether you know what an index physically is, what it costs on every write, and why a B+Tree (not a binary tree, not a hash table) is the default. For a Backend or AI engineer it is the difference between a login lookup that takes microseconds of CPU work and one that scans ten million rows on every request.
WHERE email = ... Needs an Indexusers table: 10,000,000 rows, ~100 bytes each => roughly 1 GB of heap pages
SELECT * FROM users WHERE email = '[email protected]';
No index on email:
read page 1, check every row ... read page N, check every row
cost grows LINEARLY with table size: O(n) rows examined,
even though at most 1 row matches (if email is unique).
Sorted array of (email, row location) — the "index in a file" idea:
binary search: log2(10,000,000) ~ 23 comparisons
BUT: inserting a new email in the middle means shifting up to n entries
on disk, and each of the ~23 probes may land on a different disk page.
B+Tree on email:
3-4 page reads from root to leaf, then 1 read for the row itself.
Inserts touch one leaf page (occasionally splitting it).Two things make a naive scan or a sorted array lose. A scan is O(n) in rows examined, so latency grows with the table and each request drags a large fraction of the table through the buffer pool. A sorted array gives O(log n) comparisons, but comparisons are not the real cost: disk and buffer-pool traffic is measured in pages, and a binary search over a huge file touches about 23 scattered pages, and keeping it sorted under inserts is O(n). A B+Tree fixes both: it is sorted (so lookups and ranges are logarithmic) and it is organised into page-sized nodes with a huge fan-out (so the logarithm is base hundreds, not base 2) and local updates (so inserts change one page, not the whole file).
B+Tree on email (each box = one disk page, e.g. 8 KB in PostgreSQL, 16 KB in InnoDB)
[ root: "g" | "p" ] level 0
/ | \
[ "c" | "e" ] [ "j" | "m" ] [ "s" | "w" ] level 1 (internal: keys + child pointers only)
/ | \ ... ...
[a..b]->[c..d]->[e..f]->[g..i]->[j..l]->[m..o]->[p..r]->[s..v]->[w..z] leaves
^^^^ leaves hold (key, row pointer or row) and are LINKED left-to-right
Point lookup email = 'k': root -> level 1 -> leaf (one page per level)
Range scan email BETWEEN 'j' AND 'o': descend once to the leaf holding 'j',
then walk the leaf chain sideways until past 'o'. No re-descent.
Fan-out (illustrative order of magnitude, not a benchmark):
page 8 KB, entry ~ 24-40 bytes => a few hundred children per internal page
~300 children: 300^2 = 90,000 300^3 = 27,000,000 300^4 = 8.1 billion
=> 3-4 levels cover tens of millions to billions of rows.
Upper levels are tiny and stay cached in memory, so a lookup is often
only 1-2 real disk reads.A classic B-Tree stores keys together with their values in every node, internal ones included. A B+Tree stores values (or row pointers) only in the leaves; internal nodes hold just separator keys and child pointers. That has two consequences. First, internal nodes are smaller, so more of them fit per page, the fan-out is higher, and the tree is shallower. Second, because all data sits at the leaf level and the leaves are chained, a range scan (BETWEEN, ORDER BY, LIKE 'abc%') is one descent plus a sequential walk. Most relational engines (PostgreSQL's btree, InnoDB, SQL Server) use B+Tree variants and call them "B-tree" indexes, which is why the two names are used loosely in interviews.
Depth grows with the logarithm of row count, so going from 10 million to 1 billion rows typically adds only one level. Pages also split when full and merge when sparse, which keeps the tree balanced: every leaf is at the same depth, so lookup cost is predictable and there is no "degenerate" case like an unbalanced binary tree.
hash(email) = bucket number
'[email protected]' -> hash -> bucket 4127 -> (row pointer)
'[email protected]' -> hash -> bucket 9 -> (row pointer) (neighbouring keys land far apart)
WHERE email = '[email protected]' -> one hash + one bucket probe: ~O(1)
WHERE email > 'a' -> cannot use it: hashing destroys ordering
WHERE email LIKE 'a%' -> cannot use it
ORDER BY email -> cannot use itA hash function scatters keys uniformly, which is exactly what makes equality lookups about O(1) and exactly what destroys any notion of order. There is no range scan, no sorted output, no prefix match. Engine support varies: PostgreSQL has hash indexes (crash-safe since version 10) but they are rarely preferred because a B-tree handles equality nearly as well and also handles ranges and sorting; MySQL's InnoDB does not offer user-defined hash indexes (the MEMORY engine does), though InnoDB maintains an internal adaptive hash index automatically for hot lookups. The practical default is a B+Tree, with hash reserved for pure-equality workloads on wide keys where it measurably helps.
InnoDB (MySQL) — table IS the primary key B+Tree ("clustered index")
PK tree leaf: (id=7) -> [entire row: id, email, city, age ...]
secondary tree leaf: (email='[email protected]') -> id=7 (stores the PK value)
SELECT * FROM users WHERE email='[email protected]';
1. descend secondary index -> finds id=7
2. descend PK tree with id=7 -> finds the full row (two tree descents)
PostgreSQL — table is an unordered HEAP; every index is "secondary"
heap page 42, slot 3: the row itself, identified by TID = (42, 3)
btree leaf: (email='[email protected]') -> TID (42, 3)
SELECT * FROM users WHERE email='[email protected]';
1. descend btree -> TID (42, 3)
2. read heap page 42, fetch slot 3 (index + heap fetch)A clustered index determines the physical (leaf-level) order of the rows: the row lives inside the index. There can be only one per table, because rows can be stored in only one order. In InnoDB that is always the primary key (or, if none is declared, the first unique NOT NULL index, else a hidden row id). Other indexes are non-clustered (secondary): their leaf entries store the key plus a pointer to the row. In InnoDB the pointer is the primary key value, which means a secondary lookup is two tree descents, and a long or random primary key (e.g. a random UUID) inflates every secondary index and causes page splits scattered across the tree. PostgreSQL has no clustered index in this sense: rows sit in a heap in roughly insertion order, and index entries point to a physical TID (block number and slot). PostgreSQL's CLUSTER command reorders the table once but does not maintain that order afterwards. SQL Server offers both a clustered index and a heap, chosen per table.
INSERT one row into a table with 1 PK + 3 secondary indexes:
write the row (heap page or PK leaf) 1 place
insert entry into each secondary index 3 more places, each a B+Tree leaf
(a full leaf splits: allocate page, move half, update parent)
plus WAL/redo records for every page touched
UPDATE of an indexed column: delete old index entry + insert new entry
(in PostgreSQL an update also writes a new row version, so indexes
may need new entries unless a HOT update is possible)
DELETE: mark/remove the entry in every index
Storage: every index is a full extra copy of the indexed columns + pointers,
sorted, and usually not 100% full.Reads get faster because the index is pre-organised; that organisation has to be paid for by every write. Each extra index adds another B+Tree to modify, more pages dirtied in the buffer pool, more log volume, more disk, and more background maintenance (vacuum in PostgreSQL, page merges and fragmentation in InnoDB). A table that takes 5,000 writes per second and is queried only in batches may be better off with fewer indexes than a read-mostly lookup table. The rule is not "index everything" but "index the access paths you actually use, and drop the ones you do not".
ORDER BY are one descent plus a sequential leaf walk.-- Runs in sqlite3 (SQLite uses a B+Tree for tables and indexes too)
-- Setup: 20,000 users
CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT, city TEXT, age INTEGER);
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i+1 FROM n WHERE i<20000)
INSERT INTO users SELECT i, 'user'||i||'@example.com', 'city'||(i%50), 18+(i%60) FROM n;
-- 1. No index on email: full scan
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email='[email protected]';
-- SCAN users
-- 2. Add the index, same query
CREATE INDEX idx_users_email ON users(email);
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email='[email protected]';
-- SEARCH users USING INDEX idx_users_email (email=?)
-- 3. The primary key is the table's own B+Tree (SQLite calls it rowid)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE id=777;
-- SEARCH users USING INTEGER PRIMARY KEY (rowid=?)
-- 4. Range scan uses the same index (walks the leaf chain)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email BETWEEN 'user1000@' AND 'user1999@';
-- SEARCH users USING INDEX idx_users_email (email>? AND email<?)
-- 5. Leading wildcard cannot use a B+Tree (no known starting key)
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email LIKE '%[email protected]';
-- SCAN users
-- 6. Index contains everything the query asks for: no table lookup needed
EXPLAIN QUERY PLAN SELECT email FROM users WHERE email='[email protected]';
-- SEARCH users USING COVERING INDEX idx_users_email (email=?)
-- 7. Indexes cost storage. Start again from a fresh database with only the
-- setup above (no indexes), then compare page counts (page size 4096 bytes):
PRAGMA page_count; -- 187 (table only)
CREATE INDEX idx_users_email ON users(email);
PRAGMA page_count; -- 329 (+142 pages for one email index)
CREATE INDEX idx_users_city ON users(city);
PRAGMA page_count; -- 398 (+69 pages for a city index)Q: What is an index?
A: An index is an auxiliary data structure, usually a B+Tree, that stores the indexed column values in sorted order together with pointers to the rows, so the database can find matching rows without scanning the table. It trades extra storage and slower writes for faster reads on the indexed access path. It is a performance structure only; it does not change query results, except that a unique index also enforces a constraint.
Q: How does a B-tree index work?
A: The index is a balanced tree of page-sized nodes. Internal nodes hold separator keys and child pointers; a lookup starts at the root, picks the child whose key range contains the search value, and repeats until it reaches a leaf, which holds the key and the row pointer (or the row itself). In B+Tree variants the leaves are linked, so a range scan is one descent followed by a sequential walk. Because each page holds hundreds of entries, 3-4 levels are enough for millions of rows.
Q: Why can an index improve query performance?
A: It lets the engine eliminate most of the data instead of examining it: a lookup on a 10-million-row table becomes a few page reads rather than an O(n) scan, and the sorted order also serves ORDER BY, range filters and joins. The gain depends on selectivity: it is large when the predicate matches a small fraction of rows, and small or negative when it matches a large fraction, where random row fetches can cost more than one sequential scan.
Q: Why can an index make writes slower?
A: Every INSERT and DELETE must update every index on the table, and an UPDATE of an indexed column must remove and re-insert its entry. Each of those is a B+Tree modification that may dirty additional pages, split a full leaf, and generate more WAL. So write cost grows with the number of indexes, and so do storage and maintenance overhead; that is why write-heavy tables should carry only the indexes their queries really need.
Q: Clustered vs non-clustered index?
A: A clustered index stores the full rows in the leaf pages in key order, so there can be only one per table (in InnoDB it is the primary key). A non-clustered (secondary) index is a separate structure whose leaf entries point back to the row: by primary key value in InnoDB, requiring a second descent, or by physical TID in PostgreSQL, where the table is an unordered heap. Clustered access is fast for primary key and range lookups; the cost is that inserts with random keys cause page splits, and long primary keys bloat every secondary index.
Follow-up: Why not just use a hash index for everything, since it is O(1)?
A: A hash index supports only equality; ranges, prefix matching and ordered output are impossible because hashing scatters neighbouring keys. Real workloads almost always mix equality and range predicates, so a B+Tree is the safer default, and its O(log n) with a fan-out of hundreds is only 3-4 page reads in practice. A hash index can win for pure-equality lookups on large keys, but engine support and crash-safety history vary (PostgreSQL made hash indexes WAL-logged in version 10).
Follow-up: Why is a random UUID primary key a problem in InnoDB but less so in PostgreSQL?
A: In InnoDB the table is the primary-key B+Tree and every secondary index stores the primary key, so a random 16-byte key scatters inserts across all leaf pages (more splits, worse cache locality) and makes every secondary entry larger. In PostgreSQL the heap is insertion-ordered so table writes stay sequential, but the primary-key index itself still takes random inserts and suffers similar locality costs, which is why time-ordered IDs (UUIDv7, ULID, sequences) are commonly preferred in both.
Follow-up: You added an index on a column but the query is still slow. What do you check?
A: First check with EXPLAIN whether the index is used at all: it may be ignored because the predicate matches a large fraction of rows, the column is wrapped in a function or cast, the LIKE has a leading wildcard, or statistics are stale. If it is used, check whether the query then does many random row fetches (a non-covering index), or whether the real cost is sorting, a join, or returning too many rows. The fix depends on the diagnosis, not on adding a second index by reflex.
Every "design X" answer that includes a lookup ("get user by email", "orders for customer in a date range", "messages in a chat ordered by time") should name the index that serves it, because index choice is where read latency is actually decided. In a user service the unique index on email doubles as the login lookup and the uniqueness guarantee; in a chat or feed the primary or clustering key is chosen so that a range scan returns one conversation's messages in time order from adjacent leaf pages. When a table is sharded, the shard key decides which node is asked, but the local B+Tree still decides how fast the node answers. For AI workloads, relational indexes still handle the metadata filters (tenant, document id, timestamps) around a vector search, and the same write-cost logic applies to ANN vector indexes, which are even more expensive to maintain than B+Trees. Capacity planning also has to count indexes: they often add up to as much disk and buffer-pool memory as the table itself, and the hot upper levels of the frequently used ones should fit in RAM.
The decision is to spend storage, write throughput and maintenance to buy faster reads on specific access paths. The cost is per index: each one adds work to every insert and delete on the table, competes for buffer-pool memory, and must be vacuumed or defragmented, so a table with a dozen indexes can be slower to write than the read benefit justifies. An index is the wrong choice on tiny tables (a scan of one page is cheaper than a tree descent), on low-selectivity columns such as a boolean flag (a big fraction of rows match, so the optimizer will often scan anyway), and on write-heavy tables whose queries are rare or done in bulk. Choosing a clustered key has its own trade-off: a monotonically increasing key gives cheap appends but a hot right-most leaf under heavy concurrent inserts, while a random key spreads writes but fragments the tree. The safe practice is to create indexes from real query patterns, verify them with EXPLAIN, and periodically drop the ones the workload no longer uses.