SQL Performance Explained

• A database index is a separate structure created with CREATE INDEX. It has its own disk space and holds a copy of the indexed column data — but never changes any table data.
• For every INSERT, DELETE, UPDATE, the index must stay perfectly ordered. This is achieved using two data structures: a doubly linked list and a B-tree.
• The doubly linked list handles ordering & insertions; the B-tree handles fast lookups.

Index Leaf Nodes#

• Storing index data sequentially in memory is impractical — inserting a new entry would require shifting everything after it, which is slow for large tables. A doubly linked list solves this.
• Instead of physical order, the DB creates a logical order via pointers:

[Node 11] ←→ [Node 13] ←→ [Node 18] ←→ [Node 21] ...

• Inserting a new node only updates two pointers — no data is moved:

Before:        [13] ←→ [18]
Insert 15:     [13] ←→ [15] ←→ [18]   ← only 2 pointers changed

• The linked list connects leaf nodes — the actual storage units of the index. Each leaf node maps to a DB block/page. Order is maintained at two levels:

Level 1 — Within a leaf node:   entries are sorted inside the block
Level 2 — Between leaf nodes:   blocks are chained via doubly linked list

• Each index entry in a leaf node holds two things:

[ Indexed Column Value (KEY) | ROWID / RID ]
          ↓                         ↓
   what you searched for    pointer to the actual row in the table

• How the index and table relate:

INDEX (sorted, linked)          TABLE (heap, unsorted)
┌─────────────┐                 ┌──────────────────┐
│ 11 → ROWID──┼────────────────►│ row data...      │
│ 13 → ROWID──┼──────────────┐  │ row data...      │
│ 18 → ROWID  │              └─►│ row data...      │
└──────┬──────┘                 └──────────────────┘
       │ (linked list)
┌──────▼──────┐
│ 21 → ROWID  │
│ 27 → ROWID  │
└─────────────┘

The Search Tree (B-Tree)#

• Leaf nodes alone aren’t enough — they live in physical order on disk, so the DB still needs a fast way to find the right leaf node. That’s what the B-tree solves.
• A B-tree has 3 levels:

                    [ Root Node ]           ← entry point for all searches
                   /      |      \
          [Branch]    [Branch]    [Branch]  ← narrows down the search
           /    \      /    \      /    \
         [L1]  [L2] [L3]  [L4] [L5]  [L6] ← leaf nodes (actual index data)

• Every search takes the exact same number of hops regardless of the value — always root → branch → leaf.