Indexing & Performance

1. What is the role of Indexing in a database, and how does it affect read and write performance?

An index is a separate data structure (usually a B-tree) that lets the database find rows without scanning the whole table. Think of the index at the back of a book — you go straight to the page instead of reading everything.

Reads get faster: Without an index, finding a row means scanning every row until it matches. With an index, the database can jump straight to the right location. That’s why indexed columns make SELECT and search queries dramatically faster.

Writes get slower: Every time you INSERT, UPDATE, or DELETE a row, the database must also update every index on that table. More indexes means more work per write. That’s the classic trade-off:

• Heavy-read workload → add indexes freely.
• Heavy-write workload → keep indexes minimal.

A practical rule: index columns used in WHERE, JOIN, and ORDER BY clauses, not columns that change constantly.

2. What is Indexing and why use it?

An index is a lookup structure that helps the database find rows faster, like the index of a book.

The upside: read queries (SELECT) get much faster because the database skips straight to matching rows instead of scanning the whole table.

The downside: every INSERT, UPDATE, and DELETE must also maintain the index. So write operations get slower as indexes pile up.

The trade-off is why you index the columns you actually search and join on, not everything.

3. What is the main difference between a Clustered and a Non-Clustered Index?

The difference is whether the index determines the physical order of the data.

• Clustered index — sorts and stores the actual data rows in index order. There can be only one per table, because rows can only be physically sorted one way.
• Non-clustered index — a separate structure containing index keys plus pointers (row locators) to the data rows. You can have many per table.

Analogy: A clustered index is a dictionary where words and definitions are in order together. A non-clustered index is the index at the back of a book — it points you to the right page, but the content is somewhere else.

Clustered index reads are faster (data and index in one place), but updates that change the key can force row movement.

4. Why are B-Trees or B+ Trees preferred over Binary Search Trees for database indexing?

The key reason is fewer disk I/Os. A B-tree has a high branching factor — each node holds many keys and has many children — so the tree stays very shallow.

A binary search tree with a million keys is ~20 levels deep. A B-tree with a high branching factor is only 3–4 levels deep for the same data.

Why depth matters: every level you descend is a disk read. On spinning disks (and even SSDs), random I/O is the slowest operation in a database. A B-tree turns “20 disk reads” into “3 disk reads.”

B+ trees take it further by keeping all data in the leaf level and linking the leaves, making range scans fast.

5. What is the difference between sparse and dense indexes, and hash vs B+ tree indexes?

Sparse vs dense:

• Dense index — has an index entry for every record in the table, pointing straight to it. Faster lookup (one jump), but the index is large.
• Sparse index — has an entry only for some records (e.g. one per page/block). Smaller, but lookup may require a short scan once you land on the right block.

Sparse indexes only work when records are physically sorted by the key (so you can infer the gap); dense indexes work regardless. In practice databases use dense secondary indexes plus a sparse/clustered structure at the storage level.

Hash vs B+ tree index:

• Hash index — hashes the key to a bucket. O(1) lookup for exact match (WHERE id = 5). But hashing destroys order — no range queries (WHERE age > 30), no prefix matching, no sorting by the key.
• B+ tree index — balanced tree, O(log n) lookup, and because leaves are sorted and linked, it supports range scans, ORDER BY, and prefix lookups. Slightly slower than a hash for exact match, but far more useful.

Hash:   WHERE id = 5        → O(1)  ✔ fast exact match
        WHERE id > 5        → ✘ can't
B+ tree: WHERE id = 5       → O(log n)
         WHERE id BETWEEN 5 AND 50 → ✔ leaf chain walk

The interview takeaway: hash indexes win on exact-match lookups; B+ trees win on range queries and ordering — which is why B+ trees are the default index type in almost every database, and hash indexes are the niche choice.