An index is a separate structure that maps column values to row locations (e.g. disk pages). Instead of scanning the whole table, the database uses the index to jump to matching rows — like a book index vs reading every page.
Without vs with index
flowchart TB
subgraph NoIndex["Without index"]
F1[Full table scan]
F2[Read every row]
F3[O(n) rows]
end
subgraph WithIndex["With index"]
I1[Lookup in index structure]
I2[Get row pointers]
I3[Fetch only those rows]
I4[O(log n) or O(1) lookup]
end
Common index structures
B-tree — Default in most SQL DBs. Good for range queries and equality (ORDER BY, <, >, =).
Hash index — Only equality (=). No range. Very fast for point lookups.
Composite index — Index on (A, B, C). Helps queries that filter/order by left-prefix (A), (A,B), (A,B,C).
flowchart LR
subgraph BTree["B-tree index"]
B1[Sorted keys]
B2[Range scan supported]
end
subgraph Hash["Hash index"]
H1[Key → bucket]
H2[Equality only]
end
Trade-offs
Benefit
Cost
Faster SELECT (where, order, join)
Slower INSERT/UPDATE/DELETE (index must be updated)
Less I/O for targeted queries
Extra storage for index structures
Create indexes on columns you filter, join, or order by. Avoid too many indexes on write-heavy tables. Use composite indexes for multi-column conditions; order columns by selectivity and query shape.