Indexing & B+ Trees

Indexing is a data structure technique used to quickly locate and access data in a database without having to search every row (Full Table Scan).

Without indexes, finding a single row in a 10-million-row table requires scanning all 10 million rows. With an index, it typically takes 3-4 disk reads.

---

Learning Objectives

After completing this chapter, you will be able to:

• Explain what an index is and why it’s needed.
• Differentiate between clustered and non-clustered indexes.
• Understand dense vs sparse indexes.
• Describe B+ Trees and why they are the gold standard.
• Compare B-Trees and B+ Trees.
• Understand the trade-off of indexes on write operations.
• Answer indexing interview questions.

---

What is an Index?

An index is a separate data structure that provides fast access to rows in a table based on key values.

Analogy: The index at the back of a textbook. Instead of scanning every page to find where “Normalization” is discussed, you look up “Normalization” in the index, get page numbers, and go directly there.

---

Types of Indexes

Clustered Index

• Determines the physical order of data in the table
• The data rows are stored in the same order as the index
• Only ONE per table (rows can only be physically sorted one way)
• Usually created on the Primary Key

Clustered Index (PK = Student_ID):
┌─────────┬─────────┬──────────┐
│ 101     │ Rahul   │ rahul@.. │
│ 102     │ Priya   │ priya@.. │
│ 103     │ Amit    │ amit@..  │
│ 104     │ Sneha   │ sneha@.. │
└─────────┴─────────┴──────────┘
    ↑ Data is physically stored in this order

Non-Clustered Index

• A separate structure containing index keys + pointers to data rows
• Does NOT affect physical order of data
• Multiple per table (typically up to 10-15)
• Requires an extra lookup (find key in index → fetch row from table)

Non-Clustered Index on Email:
┌─────────────────┬──────────────┐
│ Index Key (Email) │ Pointer to Row │
├─────────────────┼──────────────┤
│ amit@..         │ Row 103      │
│ priya@..        │ Row 102      │
│ rahul@..        │ Row 101      │
│ sneha@..        │ Row 104      │
└─────────────────┴──────────────┘

---

Dense vs Sparse Index

Type	Description	Example
Dense Index	Every search key value has an entry	Good for unique keys, more storage
Sparse Index	Only some key values have entries (e.g., every 10th row)	Less storage, slower for point lookups

---

B+ Tree Index

The B+ Tree is the most widely used index structure in relational databases — PostgreSQL, MySQL (InnoDB), Oracle, SQL Server, SQLite all use it.

Structure

            [50, 80]           ← Internal Nodes (keys only)
           /    |    \
     [10,30,40]  [60,70]  [90,100]  ← Leaf Nodes (keys + data/data pointers)
          |        |        |
          └────────┴────────┘ ← Leaf nodes linked (range scan!)

Component	Content
Internal Nodes	Keys + pointers to children. No data.
Leaf Nodes	Keys + actual data (or pointers to data). Linked together.
Root	Topmost node. Height balanced.

---

B-Tree vs B+ Tree

Feature	B-Tree	B+ Tree
Data storage	Internal + leaf nodes	Leaf nodes only
Leaf nodes linked	No	Yes (doubly linked list)
Range queries	Slow (traverse up and down)	Very fast (follow leaf links)
Height	Taller (fewer keys per node)	Shorter (more keys per node)
Point lookups	Average	Consistent (always reach leaf)

Why B+ Tree wins for databases: The leaf node linkage makes range queries (WHERE age BETWEEN 20 AND 30) extremely fast. You find the start point and scan forward. B-Trees require backtracking up the tree.

---

Why B+ Tree Instead of Binary Search Tree?

Factor	BST	B+ Tree
Height	O(log N) but taller	Very short (fan-out of hundreds)
Disk I/O	One node per disk read = many reads	One node = hundreds of keys = few reads
Cache efficiency	Poor	Excellent
Self-balancing	Yes (AVL/Red-Black)	Yes (automatic)

A B+ Tree with fan-out 100 and 10 million rows needs only 4 levels (root + 3 internal = 4 disk reads). A BST would need ~24 reads.

---

Index Trade-Offs

Operation	Without Index	With Index
SELECT by key	Full scan (O(N))	O(log N)
Range query	Full scan (O(N))	O(log N + result size)
INSERT	Fast (append)	Also update index
UPDATE key	Fast	Also update index
DELETE	Fast	Also update index

The cost: Every INSERT, UPDATE, DELETE must update ALL indexes on the table. More indexes = slower writes.

---

Interview Deep Dive

---

Key Takeaways

• Indexes speed up reads at the cost of slower writes and extra storage.
• Clustered Index determines physical sort order — one per table.
• Non-Clustered Index is a separate structure with pointers — multiple allowed.
• B+ Tree is the standard index structure — leaf nodes linked for fast range scans.
• B+ Tree beats B-Tree and BST for database workloads due to lower height and linked leaves.
• Dense index → every key has entry. Sparse index → some keys.
• Covering index can answer a query without touching the table.