An index is an auxiliary data structure (usually a B-tree or hash) that lets the DBMS find rows without scanning the whole table. It is like the index of a book: instead of reading every page, you jump straight to the right one. Indexes dramatically speed up reads but add cost to writes.
How an index helps (and costs)
Without an index, a query that filters on a column does a full table scan — O(n). A B-tree index turns that lookup into roughly O(log n). The cost: every INSERT/UPDATE/DELETE must also update the index, and indexes take extra storage.
Clustered vs non-clustered
| Type | Idea |
|---|---|
| Clustered | table rows are physically stored in index order; one per table |
| Non-clustered | a separate structure pointing to the rows; many allowed |
⚡ The edge
- Indexes make reads faster but writes slower — so index the columns you frequently search/join on, not everything.
- A clustered index determines the physical row order (only one possible); non-clustered indexes are separate lookups (you can have many).
Worked example
'Why not index every column?'
- Each index speeds up reads on its column but must be maintained on every write.
- Too many indexes slow down INSERT/UPDATE/DELETE and waste storage.
- So you index selectively — columns used in WHERE, JOIN and ORDER BY — and measure the trade-off.
Answer: Indexes cost write performance and storage, so you index only frequently-queried columns.
Worked example
'What data structure backs most database indexes, and why?'
- Most use a B-tree (or B+ tree) because it stays balanced and shallow.
- That gives O(log n) search, insert and delete, and supports range queries efficiently (leaves are linked).
- Hash indexes give O(1) equality lookups but can't do range scans, so B-trees are the default.
Answer: A balanced B+ tree — O(log n) lookups plus efficient range scans, which hashes can't do.
⚠ Watch out
- Indexes are not free: they slow writes and consume storage.
- There can be only one clustered index per table (it dictates physical order); many non-clustered ones are allowed.
- An index on a low-selectivity column (e.g. a boolean) often isn't worth it.