Indexing in DBMS — B-Trees, Clustered vs Non-Clustered, When to Index

Without an index, finding one row means checking every row (a full table scan). With 10 crore rows, that's slow. An index works like the index at the back of a book: it tells the database exactly where to look.

1. How a B-tree index works

• The index keeps the column's values sorted in a balanced tree.
• Each step down the tree cuts the search space a lot, so finding a value takes about log(n) steps.
• For 10 crore rows, that's around 4–5 page reads instead of millions.
• Sorted order also speeds up ORDER BY, range queries (BETWEEN, >), MIN/MAX.

2. Creating an index

CREATE TABLE orders (order_id INT PRIMARY KEY, customer_id INT, city VARCHAR(20), amount INT, created DATE);
INSERT INTO orders VALUES (1, 7, 'Jaipur', 499, '2026-11-01'), (2, 3, 'Pune', 1299, '2026-11-02'), (3, 7, 'Jaipur', 250, '2026-11-03');
CREATE INDEX idx_orders_customer ON orders(customer_id);
SELECT order_id, amount FROM orders WHERE customer_id = 7 ORDER BY order_id;

order_id | amount
1 | 499
3 | 250

The query looks the same — the database decides to use the index. Use EXPLAIN (MySQL/PostgreSQL) to see whether it does.

Primary keys and UNIQUE columns get an index automatically.

3. Clustered vs non-clustered

4. Composite indexes and the leftmost-prefix rule

An index on (city, created) is sorted by city, then by date within each city.

• ✅ WHERE city = 'Jaipur' — uses it
• ✅ WHERE city = 'Jaipur' AND created > '2026-11-01' — uses it fully
• ❌ WHERE created > '2026-11-01' alone — usually can't use it (date isn't the first column)

Put the column used most often (and with equality) first.

5. When indexes don't help

• Small tables (a scan is already fast).
• Columns with very few distinct values (e.g. gender) — the database often scans anyway.
• Functions on the column: WHERE YEAR(created) = 2026 can't use an index on created; write created >= '2026-01-01' AND created < '2027-01-01' instead.
• LIKE '%text' (leading wildcard).

6. The cost of indexes

• Extra disk space.
• Slower INSERT / UPDATE / DELETE, because every index must be updated too.

So index columns you search, join or sort by often — not every column.

Common mistakes

• Indexing every column "to be safe".
• Writing queries that wrap indexed columns in functions.
• Ignoring column order in composite indexes.

Quick recap

• Index = sorted B-tree → about log(n) lookups instead of a full scan.
• One clustered index (row order); many non-clustered (pointers).
• Composite index: leftmost-prefix rule.
• Indexes speed up reads but cost space and slow down writes.