Big Picture: What is an Index Structure?

Most database indexes (like MySQL InnoDB, PostgreSQL B-tree indexes, SQL Server) are stored as a B-tree or B+ tree structure.

Think of it as a tree — like an upside-down real tree:

• The root is at the top — entry point.
• Branches are inside — help guide to the right place.
• Leaves are at the bottom — actual data or pointers to data.

---

Here’s a simpler sketch:

            [ ROOT PAGE ]
                /     \
       [ BRANCH PAGE ] [ BRANCH PAGE ]
         /     \          /      \
 [LEAF PAGE] [LEAF PAGE] [LEAF PAGE] [LEAF PAGE]

Root Page: Entry point for the index.

Branch Pages (Internal Nodes): Hold ranges and point to next levels.

Leaf Pages: Store sorted key values + pointers to actual table rows (or row data).

Example with Data

Let’s say you have a table indexed on customer_id:

• Root Page:
  • Says:
    • If customer_id < 5000, go left.
    • If customer_id ≥ 5000, go right.
• Branch Pages:
  • Further divide the range:
    • 0-2500 → go left
    • 2501-4999 → go right
• Leaf Pages:
  • Actually have customer IDs:

Leaf 1: [100, 200, 300, 400]
Leaf 2: [500, 600, 700, 800]
Leaf 3: [5000, 5200, 5400]
Leaf 4: [6000, 6500, 7000]

Simpler ASCII Tree

             [ 5000 ]
            /        \
    [ 2500 ]         [ 6000 ]
    /      \         /     \
[100-400][500-800][5000-5400][6000-7000]

At the root level, it decides:

• Numbers less than 5000 go to the left.
• Numbers 5000 and higher go to the right.

At the branch level:

• Numbers less than 2500 go further left.
• Numbers between 2500 and 5000 go to the next.

At the leaf level:

• Sorted keys in each leaf.

What’s Inside One Page?

Each Page (like [100, 200, 300, 400]) is one Index Page — a block of memory holding multiple sorted keys.

• In a real DB, a page could be 8 KB, and hold maybe 100–500 keys (depends on size).
• Database reads one whole page at a time — not individual rows!

---

Step-by-Step How Search Works

If you search for customer_id = 5400:

1. Start at the root page — 5400 is ≥ 5000 → go right.
2. At next level (branch page) — 5400 is < 6000 → go left.
3. Reach leaf page [5000, 5200, 5400] — find 5400.

✅ Found — and very fast — because it only reads a few pages, not the whole table!

In Summary

Level	What it holds
Root Page	Entry points (top level keys).
Branch Pages	Midpoints — guide search direction.
Leaf Pages	Actual sorted key values (and row pointers).
Page	A block (8 KB) containing multiple keys.

---

Simple Picture

📚 A book with:

• Table of contents (root).
• Chapters (branches).
• Pages with content (leaves).