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

Source: https://skills101.in/learn/dbms-sql/database-indexing — Skills101 free tutorial (DBMS & SQL). Updated 2026-11-09.

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.

![A B-tree index: the root holds 50; the left child 20 | 35 and right child 65 | 80; leaves hold sorted keys. Finding 70 goes 50 → 65 | 80 → leaf in a few steps instead of scanning everything](https://skills101.in/learn-img/dbms-sql/index-tree.svg)

## 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

```sql
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;
```

```text
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

| | Clustered | Non-clustered |
|---|---|---|
| What it is | the table rows themselves are stored in index order | a separate structure with pointers to rows |
| How many per table | **one** (rows can be sorted only one way) | many |
| Example | MySQL InnoDB primary key | an index on `email` |
| Lookup | data is right there | index → pointer → row (an extra step) |

## 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.


Practice quiz and free certificate: https://skills101.in/learn/dbms-sql/database-indexing