B-Tree Indexes

Lecture 8 · a B-tree is a balanced tree index where both internal nodes and leaf nodes can store search keys and record pointers. Balanced means all leaf nodes are at the same level, so the search path length is almost equal for all records.

Why tree-based indexing?

B-tree and B+ tree are tree-based indexing structures used in databases to search, insert, delete and retrieve records efficiently. They are used because simple indexes may become very large — and if the index is very large, searching the index itself becomes costly. B-trees solve this by organizing index entries in a balanced tree structure.

Without indexing
The DBMS may search row by row:
101 → 102 → 103 → 104 → 105 → 106
6-step search

With B-tree indexing
The DBMS follows a path from the root node to the required value.
2-step search

Storage structure

A B-tree is stored as a separate entity/table. It stores the key and a pointer — not the entire table. In this case: Emp_ID and the address of the row.

EMPLOYEE table

Emp_ID	Name	Department	Salary	Memory Location
10	Rahim	CSE	50000	v53
11	Karim	EEE	45000	v54
12	Nila	CSE	55000	v55
13	Hasan	BBA	40000	..
14	Rony	CSE	60000	..
15	Mina	EEE	52000	..
16	Abdul	CSE	50000	..
17	Kuddus	EEE	45000	..
18	Nilima	CSE	55000	..
19	Hasnain	BBA	40000	..
20	Robi	CSE	60000	..
21	Mina	EEE	52000	..
22	Nina	CSE	55000	..

One B-tree node

Top row = the actual key (Emp_ID). Bottom row = the physical address/pointer to the data row stored in memory.

Construction — Emp_ID 10 … 22, max 3 keys per node

Split rule used in this course. Insert first; if a node then holds more than 3 keys, split it. Split on the middle — N/2 (ceiling) with N = 4 keys → the 3rd key is promoted to the parent, the first two stay in the left node and the last one goes to the right node.

Insert	Action	Resulting shape
10, 11, 12	Add keys in sorted order — the single (root) node fills up.	`[10 11 12]`
13	The node now has 4 keys → split. Split on the middle, N/2 (ceiling) with N = 4 → the 3rd key, which is 12. 12 moves up and becomes the root.	`[12] → [10 11] · [13]`
14	Goes into the right leaf.	`[12] → [10 11] · [13 14]`
15	Still fits (3 keys max).	`[12] → [10 11] · [13 14 15]`
16	[13 14 15 16] overflows → split, promote 15 into the root.	`[12 15] → [10 11] · [13 14] · [16]`
17	Goes into the last leaf.	`[12 15] → … · [16 17]`
18	Still fits.	`[12 15] → … · [16 17 18]`
19	[16 17 18 19] overflows → split, promote 18.	`[12 15 18] → [10 11] · [13 14] · [16 17] · [19]`
20	Goes into the last leaf.	`[12 15 18] → … · [19 20]`
21	Still fits.	`[12 15 18] → … · [19 20 21]`
22	[19 20 21 22] overflows → promote 21; the root [12 15 18 21] now overflows too → split it and promote 18. The height grows.	`final tree below`

Final B-Tree

B-Tree of height 3. Every key 10–22 appears exactly once — 18, 12, 15 and 21 live in internal nodes and are not repeated in the leaves.

Read it back: root [18] → left [12 15] → leaves [10 11] [13 14] [16 17]; right [21] → leaves [19 20] [22]. All leaves are at the same level, so the tree is balanced.

Search for 16: 16 < 18 → left; 15 < 16 < … → third child of [12 15] → leaf [16 17] — three node reads. Search for 18: found at the root — one read. That “a search may end at an internal node” is a defining property of the B-tree.

The tree only grows at the root. The height increased exactly once — when inserting 22 forced the root itself to split. That is why all leaves always stay on the same level.

Practice online: planetscale.com — B-trees and database indexes
Next: B+ Tree indexes →