How do indexing work in background
- Indexing is about finding the right data page quickly on disk. Start with how the database stores rows, then see B-trees and B+ trees.
How the database stores data (data pages and data blocks)
logical representation of db:-
studentId studentName
12 s1
32 s2
34 s3
59 s4
54 s5
95 s6
This is the logical table. On disk the engine does not store one giant spreadsheet; it stores pages.
Data page (~8 KB)
- Rows are grouped into data pages (often about 8 KB).
- Each data page contains (top to bottom):-
┌─────────────────┐
│ header │
├─────────────────┤
│ data rows │
├─────────────────┤
│ offset │
└─────────────────┘
- header — metadata of the page (page number, free space, etc.)
- data rows — the actual row bytes from the table
- offset — an array; each entry is a pointer (offset) into the data rows section for one row
┌─────────────────┐
│ header │
├─────────────────┤
│ row1, row2, row3│ ← data rows
├─────────────────┤
│ r1 , r2 , r3 │ ← offset
└─────────────────┘
Data block (disk)
- Disk (or SSD) is read and written in blocks — the usual unit for one I/O operation.
- A data page is stored inside a block (often one page fits one block, e.g. 8 KB).
- Many blocks sit on disk; they are not all next to each other, so reading random pages one by one is slow.
disk
├── block 1 → data page 1 (e.g. studentId 12)
├── block 2 → data page 2 (e.g. 32, 34)
├── block 3 → data page 3 (e.g. 54, 59)
└── ...
Where “memory” fits
- Permanent storage is on disk (pages inside blocks).
- When you run a query, the engine loads needed pages into RAM (buffer pool / cache), works on them, and may write dirty pages back to disk.
- Indexing keeps a separate structure (a B+ tree) so the engine knows which block / page to load instead of scanning every page.
B-tree rules
- A B-tree is a tree with these useful rules:
- All leaf nodes are at the same level.
- A node contains pointers to its child nodes and keys (keys kept sorted inside the node).
- For an order m B-tree, a node has at most m child pointers and at most m − 1 keys.
Dry run: order 3, keys 4, 2, 6, 11, 50, 19, 56
Let us store 4, 2, 6, 11, 50, 19, 56 in a B-tree of order 3 (max 2 keys per node).
Insert 4
[ 4 ]
insert 2
[ 2 , 4 ]
insert 6
Node [2, 4, 6] would hold three keys — too many. Split. Middle key 4 moves up:
[ 4 ]
/ \
[ 2 ] [ 6 ]
insert 11
11 goes to the right of 4 (with 6):
[ 4 ]
/ \
[ 2 ] [ 6 , 11 ]
insert 50
Right leaf [6, 11, 50] overflows. Promote 11. Root becomes [4, 11]:
[ 4 , 11 ]
/ | \
[ 2 ] [ 6 ] [ 50 ]
insert 19
19 goes on the right branch (before 50):
[ 4 , 11 ]
/ | \
[ 2 ] [ 6 ] [ 19 , 50 ]
insert 56
Right leaf [19, 50, 56] overflows. Promote 50. Rebalance until the tree looks like this (same as your final diagram):
[ 11 ]
/ \
[ 4 ] [ 50 ]
/ \ / \
[ 2 ] [ 6 ] [ 19 ] [ 56 ]
All leaves stay one level below the root’s subtrees. Search: compare key, follow one pointer, repeat.
B+ tree
What are B+ trees? — The leaf nodes are linked with another pointer (a sibling link left-to-right).
Same keys as above; leaves form a chain for range scans (WHERE id BETWEEN 6 AND 56):
[ 11 ]
/ \
[ 4 ] [ 50 ]
/ \ / \
[2] [6] [19] [56]
leaf chain: 2 <-> 6 <-> 19 <-> 56
- Internal nodes — routing only (copies of keys).
- Leaves — indexed values plus pointer to data (row / page).
- Engines such as MySQL (InnoDB) and PostgreSQL (B-tree index) use B+ trees, not plain B-trees, for most indexes.
Dry run: index on studentId → data pages
Index on studentId (B+ tree grows as rows are inserted).
12
index: 12 ──► page 1 (12)
12, 32
index: 12 , 32 ──► page 1 (12 , 32)
insert 34 — index and data page split
Data page was full after 12, 32. New row 34 splits storage. Index promotes 32:
index: [ 32 ]
/ \
12 32 , 34
| |
page 1 page 2
(12) (32 , 34)
block 1 block 2
insert 59
index: [ 32 , 34 ]
/ | \
12 32,34 59
| | |
page 1 page 2 page 3
block 1 block 2 block 3
insert 54
54 sits between 34 and 59. Same index shape; page 3 holds two rows:
index: [ 32 , 34 ]
/ | \
12 32,34 54 , 59
| | |
page 1 page 2 page 3
(54 , 59)
insert 95 — leaf split, root split
Leaf page 3 would hold [54, 59, 95] — three keys (too many for order 3). Split leaf; promote 59 into the index. Root [32, 34, 59] has three keys — split again; promote 34.
Final index (internal + leaves):
index: [ 34 ]
/ \
[ 32 ] [ 59 ]
/ \ / \
12 32,34 54 95
| | | |
page 1 page 2 page 3 page 4
block 1 block 2 block 3 block 4
(12) (32,34) (54) (95)
B+ leaf chain (sibling pointers at leaf level):
12 <-> 32,34 <-> 54 <-> 95
| | | |
page 1 page 2 page 3 page 4
Lookup studentId = 95: root 34 (go right) → 59 (go right) → leaf 95 → page 4 → offset → row.
- With a B+ tree, keys in index leaves are sorted and linked; each leaf points at a data page on disk, so retrieval touches fewer blocks than a full table scan.
- Each leaf stores the indexed column (e.g. studentId) and a pointer to the data page (and row slot / PK, depending on engine).
Types of Index:-
clustered indexing:-
- By default this is usually the primary key (e.g. InnoDB clusters the table by PK).
- Table rows are ordered by that key in the data pages.
- Pointers to rows inside a page live in the offset array; slots are managed in order for that page’s rows.
┌─────────────────┐
│ header │
├─────────────────┤
│ row1, row2, row3│
├─────────────────┤
│ r1 , r2 , r3 │
└─────────────────┘
Non clustered indexing:-
- Maintains a separate B+ tree (not the table row order itself).
- Index can be on another column, e.g. studentName.
- Leaf holds index key + locator back to the row (often the primary key or page + offset).
Caution:-
Indexing should be created in a careful manner.
- If you create an index on every column, the engine maintains a B+ tree per index — that uses memory and disk.
- Write operations (INSERT, UPDATE, DELETE) cost more: the engine must update data pages and each index tree that covers changed columns.
Index columns you actually filter or join on; do not index everything by default.
Revision map (one glance)
B-tree order m → max m pointers, m−1 keys, same leaf level, split on overflow
B+ tree → leaves linked; leaf = key + pointer to data page
Table → 8 KB pages: header | data rows | offset
Disk → pages in blocks; index reduces random I/O
Clustered → usually PK, row order tied to index
Non-clustered → extra B+ tree (e.g. name) → then find row
Top comments (0)