Indexes

An index is a separate data structure that stores a sorted (or hashed) copy of one or more columns together with pointers to the corresponding table rows, so the database can find rows without scanning the whole table.

Concept

Analogy: the index at the back of a textbook. To find "normalization", you look it up alphabetically and jump to page 312 instead of reading all 600 pages.

Without index (full table scan)            With index on customers(email)
read row 1 ... compare                     search B-tree: 3–4 page reads
read row 2 ... compare                          │
...                                             ▼
read row 10,000,000 ... compare            row pointer → fetch 1 row

Why It Matters

An indexed lookup on a 100-million-row table may read a handful of pages instead of millions.

Indexes enforce uniqueness (PRIMARY KEY, UNIQUE).

Indexes speed up joins, sorting, and grouping.

But every index slows down INSERT, UPDATE, and DELETE and uses storage. Index design is a trade-off — and one of the most valuable practical database skills.

Syntax

CREATE [UNIQUE] INDEX index_name
ON table_name (column1 [ASC|DESC], column2, ...);

DROP INDEX index_name;                      -- PostgreSQL, Oracle, SQLite
DROP INDEX index_name ON table_name;        -- MySQL, SQL Server
ALTER TABLE table_name DROP INDEX index_name;  -- MySQL alternative

Example

19.1 How indexes work: the B-tree Most indexes are B-tree (balanced tree, specifically B+tree) structures:

Balanced: every leaf is the same depth; lookups cost O(log n) page reads. A B-tree with fan-out of a few hundred keys per page reaches billions of rows in 3–5 levels.

Sorted: supports =, <, >, BETWEEN, LIKE 'prefix%', ORDER BY, MIN/MAX.

Leaves are linked: range scans walk leaf-to-leaf.

Lookup WHERE customer_id = 57: root → internal page → leaf → row pointer → table row. Typically 3–4 page reads.

19.2 Hash index concept A hash index applies a hash function to the key and stores entries in buckets.

Equality and range queries Equality only (=) Supports ORDER BY, prefix LIKE General purpose default

Specialized (PostgreSQL USING HASH, MySQL MEMORY engine, in-memory tables in SQL Server)

Other index types: bitmap (Oracle; low-cardinality columns in warehouses), GIN/GiST (PostgreSQL; full-text, JSONB, arrays, geometry), full-text indexes (MySQL, SQL Server), columnstore (SQL Server, analytics), BRIN (PostgreSQL; very large naturally ordered tables like time-series logs).

19.3 CREATE INDEX and DROP INDEX 19.4 Unique indexes Enforces uniqueness like a UNIQUE constraint (UNIQUE constraints are implemented with unique indexes). Partial/filtered unique indexes enforce conditional uniqueness:

19.5 Composite (multi-column) indexes and the leftmost-prefix rule

The index is sorted by customer_id, then by order_date within each customer — like a phone book sorted by last name, then first name.

Can use the index efficiently?

WHERE customer_id = 1 Yes (leading column) WHERE customer_id = 1 AND order_date >= DATE '2026-02-01' Yes (both columns)

WHERE customer_id = 1 ORDER BY order_date DESC Yes (seek + already sorted) WHERE order_date >= DATE '2026-02-01'

Usually not for seeking (not the leading column; may scan the whole index; Oracle/MySQL 8 have "skip scan")

WHERE customer_id > 1 AND order_date = DATE '2026-03-10' Seek on customer_id range only; order_date filtered afterwards

Column order guideline: put equality-filtered columns first, then range or sort columns. Among equality columns, consider which combinations of queries you need to support.

19.6 Clustered vs non-clustered indexes Clustered index: the table rows themselves are stored in the index's order (the leaf level is the data). Only one per table.

Non-clustered (secondary) index: a separate structure with keys and pointers (row IDs or clustered-key values) back to the table. Many per table.

Number per table Many (SQL Server up to 999) Actual data rows Key + row locator Defines row order

Needs a "key lookup"/"bookmark lookup" to fetch non-indexed columns

Narrow, unique, static, ever-increasing (e.g., identity) Columns used in WHERE/JOIN/ORDER BY DBMS behavior:

SQL Server: PRIMARY KEY creates a clustered index by default; you can choose another column.

MySQL InnoDB: the table is always clustered on the PRIMARY KEY (or first UNIQUE NOT NULL, or a hidden row ID). Secondary indexes store PK values, so a wide PK makes all secondary indexes larger.

PostgreSQL: tables are heaps (not clustered); all indexes are secondary. CLUSTER reorders once but is not maintained.

Oracle: heap tables by default; Index-Organized Tables (IOT) are clustered.

SQLite: tables are clustered by rowid; WITHOUT ROWID tables are clustered by PK.

19.7 Covering indexes A covering index contains all columns a query needs, so the database answers the query from the index alone (an index-only scan) without visiting the table.

INCLUDE columns are stored only at the leaf level (not sorted, not usable for seeking), keeping the upper tree small.

19.8 Selectivity and cardinality Cardinality (of a column): the number of distinct values. email has high cardinality; gender or status has low cardinality.

Selectivity (of a predicate or index): the fraction of rows returned. selectivity = rows matched / total rows. Lower fraction = more selective = better index candidate.

Distinct values in 10M rows Rows per value Index useful for equality?

customer_id in orders status (5 values) Poor alone (except for rare values, e.g., 'FAILED' = 0.1%) is_deleted (boolean, 99% false)

Useful only via partial index WHERE is_deleted = true Rule of thumb: if a predicate returns more than roughly 5–20% of a table, a full scan is often cheaper than many random index lookups. The optimizer decides using statistics (histograms of value distribution), which must be kept up to date (ANALYZE in PostgreSQL, ANALYZE TABLE in MySQL, UPDATE STATISTICS in SQL Server, DBMS_STATS in Oracle).

19.9 When indexes help Columns in selective WHERE conditions: WHERE email = ?, WHERE vin = ?.

JOIN columns, especially foreign keys: orders.customer_id, order_items.product_id.

ORDER BY columns for Top-N queries: an index on (created_at DESC) returns the latest 10 rows without sorting.

GROUP BY columns (sorted input enables streaming aggregation).

MIN/MAX on indexed columns (read one end of the index).

Why index foreign keys: joins on them become index seeks, and deleting/updating a parent row must check for child rows — without an index that check scans the child table (and in some DBMSs takes broader locks).

19.10 When indexes hurt Writes: each INSERT must add an entry to every index; each UPDATE of an indexed column updates the index; each DELETE removes entries. A table with 12 indexes may insert several times slower.

Storage and memory: indexes consume disk and buffer-cache space, pushing useful data out of memory.

Low-selectivity columns: index scans + lookups can be slower than a sequential scan.

Small tables: a few pages are faster to scan than to navigate an index.

Unused indexes: pure overhead.

Maintenance: fragmentation/bloat requires rebuilds/reindexing in write-heavy tables.

Queries that cannot use a normal index on the column (non-sargable):

Fixes: rewrite the predicate (total_amount > 10000 / 1.18), store normalized data (lowercase email), or create an expression/function-based index:

Symptoms: slow inserts/updates, large database size, many indexes with overlapping leading columns, indexes never used.

Finding unused indexes:

19.12 Indexing strategy checklist Yes (almost always) Selective WHERE equality Range filter on dates in large tables

Yes, often in a composite with an equality column first ORDER BY + LIMIT on large tables Yes, matching the sort order

Only as a partial/filtered index, or in a composite Columns updated very frequently Tiny lookup tables Usually unnecessary beyond the PK

[ Root: 40 | 80 ]
                   /             |              \
          [10 | 20 | 30]   [50 | 60 | 70]    [90 | 100]       ← internal pages
           /   |   |  \      ...                ...
   [leaf: 1..9] [10..19] [20..29] [30..39] ... [100..120]      ← leaf pages (sorted keys + row pointers)
        ↔          ↔        ↔        ↔                         ← leaves linked for range scans

hash('ananya@example.com') = 7  → bucket 7 → row pointer

CREATE INDEX ix_orders_customer_id ON orders (customer_id);
CREATE INDEX ix_orders_order_date  ON orders (order_date);

-- PostgreSQL: build without blocking writes
CREATE INDEX CONCURRENTLY ix_orders_status ON orders (status);

-- SQL Server: online build (Enterprise edition)
CREATE INDEX ix_orders_status ON orders (status) WITH (ONLINE = ON);

DROP INDEX ix_orders_status;                -- PostgreSQL / Oracle / SQLite
DROP INDEX ix_orders_status ON orders;      -- MySQL / SQL Server

CREATE UNIQUE INDEX ux_customers_email ON customers (email);

-- PostgreSQL / SQLite: only one ACTIVE subscription per user
CREATE UNIQUE INDEX ux_one_active_sub ON subscriptions (user_id) WHERE status = 'ACTIVE';

-- SQL Server: filtered index
CREATE UNIQUE INDEX ux_one_active_sub ON subscriptions (user_id) WHERE status = 'ACTIVE';

CREATE INDEX ix_orders_cust_date ON orders (customer_id, order_date);

Clustered index on emp_id                     Non-clustered index on last_name
[leaf pages contain full rows]                [leaf: last_name → pointer]
 1 | Asha   | Rao    | ...                     Das    → emp_id 6
 2 | Vikram | Shah   | ...                     Iyer   → emp_id 3
 3 | Neha   | Iyer   | ...                     Joshi  → emp_id 7
 ...                                           ... (then lookup in clustered index)

-- Query
SELECT order_date, total_amount FROM orders WHERE customer_id = 2;

-- Covering index: key columns + included columns
CREATE INDEX ix_orders_cust_cover ON orders (customer_id) INCLUDE (order_date, total_amount);  -- SQL Server, PostgreSQL 11+
CREATE INDEX ix_orders_cust_cover ON orders (customer_id, order_date, total_amount);         -- MySQL, Oracle, SQLite (add as key columns)

-- Indexing foreign keys (not automatic in PostgreSQL, SQL Server, Oracle)
CREATE INDEX ix_order_items_product_id ON order_items (product_id);
CREATE INDEX ix_employees_dept_id      ON employees (dept_id);
CREATE INDEX ix_employees_manager_id   ON employees (manager_id);

WHERE UPPER(email) = 'BEN@EXAMPLE.COM'         -- function on column
WHERE total_amount * 1.18 > 10000               -- arithmetic on column
WHERE name LIKE '%Carter'                       -- leading wildcard
WHERE CAST(customer_id AS VARCHAR(10)) = '2'    -- conversion on column
WHERE phone = 9876543210                        -- implicit conversion if phone is VARCHAR

Expected Result

Before the index:

After CREATE INDEX ix_orders_customer_id ON orders (customer_id);:

The estimated cost drops by about 500×. (Exact numbers vary with data and configuration.)

-- PostgreSQL, after loading 1,000,000 orders
EXPLAIN SELECT * FROM orders WHERE customer_id = 42;

Seq Scan on orders  (cost=0.00..20834.00 rows=10 width=40)
  Filter: (customer_id = 42)

Index Scan using ix_orders_customer_id on orders  (cost=0.42..44.60 rows=10 width=40)
  Index Cond: (customer_id = 42)

Common Mistakes

Indexing every column "just in case".

Creating single-column indexes on each column instead of one composite index matching the query.

Wrong column order in composite indexes.

Forgetting to index foreign keys.

Wrapping indexed columns in functions or causing implicit conversions.

Assuming an index is always used — the optimizer may correctly choose a full scan.

Not updating statistics after large data loads.

Creating indexes on huge production tables with blocking DDL (use CONCURRENTLY/ONLINE options).

Best Practices

Design indexes from actual query patterns (WHERE, JOIN, ORDER BY) and verify with EXPLAIN.

Prefer a small number of well-designed composite/covering indexes.

Keep clustered keys narrow, unique, and increasing.

Review index usage statistics periodically and drop unused indexes.

Name indexes consistently: ix_<table>_<cols>, ux_<table>_<cols> for unique.

Interview Relevance

Very high: "What is an index and how does it work?", "Clustered vs non-clustered?", "Why not index every column?", "What is a covering index?", "Composite index column order?", "What is cardinality/selectivity?", "Why is my index not used?", "B-tree vs hash?".

Practice Questions

Which index would you create for SELECT * FROM orders WHERE status = 'PENDING' ORDER BY order_date LIMIT 20 if PENDING orders are 1% of rows?

Explain why WHERE YEAR(order_date) = 2026 may not use an index on order_date, and rewrite it.

Given index (country, city), which of these can seek: country = 'India', city = 'Pune', country = 'India' AND city = 'Pune'?

Why can a wide primary key hurt all secondary indexes in MySQL InnoDB?

Design a covering index for SELECT product_id, SUM(quantity) FROM order_items GROUP BY product_id.