How a B-tree index works
40 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A MySQL index is not a simple sorted list: it is a B-tree, a short and wide tree of pages that keeps keys in sorted order. Its shape is the reason one lookup among a crore rows reads only three or four pages.
Sorted keys in a tree of pages
A B-tree is a balanced tree of pages that keeps keys in sorted order: leaf pages at the bottom hold every key, pages above hold signposts, and one root page sits on top. A page is the 16 KB block InnoDB reads and caches.
InnoDB reads data in 16 KB pages, so the cost of a query is the number of pages it reads. The script below counts the pages of an index; the tree shows one root page above three leaf pages.
A tiny B-tree: one root page and three leaf pages
Step 1 of 3
Example 1 · How many pages does an index use?
SELECT @@innodb_page_size AS page_size_bytes;
SET SESSION cte_max_recursion_depth = 100000;
CREATE TABLE train_bookings ( booking_id INT PRIMARY KEY, pnr CHAR(10) NOT NULL, train_no INT NOT NULL, travel_date DATE NOT NULL, fare DECIMAL(8,2) NOT NULL);
INSERT INTO train_bookings (booking_id, pnr, train_no, travel_date, fare)WITH RECURSIVE seq AS ( SELECT 1 AS n UNION ALL SELECT n + 1 FROM seq WHERE n < 100000)SELECT n, CAST(4210000000 + n * 7919 AS CHAR), 12000 + n % 500, DATE '2026-01-01' + INTERVAL (n % 365) DAY, 200 + (n * 37) % 2800FROM seq;
CREATE INDEX idx_bookings_pnr ON train_bookings (pnr);ANALYZE TABLE train_bookings;
SELECT index_name, stat_name, stat_valueFROM mysql.innodb_index_statsWHERE database_name = DATABASE() AND table_name = 'train_bookings' AND stat_name IN ('n_leaf_pages', 'size')ORDER BY index_name, stat_name;+-----------------+ | page_size_bytes | +-----------------+ | 16384 | +-----------------+ +-------------------------+---------+----------+----------+ | Table | Op | Msg_type | Msg_text | +-------------------------+---------+----------+----------+ | practice.train_bookings | analyze | status | OK | +-------------------------+---------+----------+----------+ +------------------+--------------+------------+ | index_name | stat_name | stat_value | +------------------+--------------+------------+ | PRIMARY | n_leaf_pages | 293 | | PRIMARY | size | 353 | | idx_bookings_pnr | n_leaf_pages | 127 | | idx_bookings_pnr | size | 161 | +------------------+--------------+------------+
What this code does
@@innodb_page_sizeis 16384 bytes, the 16 KB default.ANALYZE TABLErefreshes the statistics InnoDB keeps about each index;mysql.innodb_index_statsstores them.n_leaf_pagesis the number of leaf pages, andsizeis all pages of the index. Your numbers may differ a little.PRIMARYholds the full rows, so its leaves store about 340 bookings per page.idx_bookings_pnrholds only the PNR and thebooking_id, so its entries are smaller and it needs fewer pages.- About 300 leaf pages need only one root page above them, so either tree is probably just two levels tall: a lookup reads two pages out of hundreds.
Why a tree of pages and not one long sorted list? A sorted list of a crore keys fills thousands of pages, and even binary search would read about 15 of them. Because one page holds hundreds of signposts, each level divides the search by hundreds, not by 2.
Finding one key in a few steps
An index dive is one walk from the root page down to a leaf page, following at each level the signpost whose range holds the key. It reads one page per level, so its cost is the height of the tree, not the size of the table.
To find one key, MySQL walks from the root page down to a leaf. The script below compares the pages read by an index lookup with the pages read by a full scan.
Finding key 40
Step 1 of 3
- key
- 40
- pages
- 1
Example 2 · Pages read: index lookup versus full scan
-- A simplified model: about 300 keys fit in one page.WITH sizes AS ( SELECT 1000 AS table_rows UNION ALL SELECT 100000 UNION ALL SELECT 10000000 UNION ALL SELECT 1000000000)SELECT table_rows, CEIL(LOG(300, table_rows)) AS pages_read_with_index, CEIL(table_rows / 300) AS pages_read_by_full_scanFROM sizesORDER BY table_rows;+------------+-----------------------+-------------------------+ | table_rows | pages_read_with_index | pages_read_by_full_scan | +------------+-----------------------+-------------------------+ | 1000 | 2 | 4 | | 100000 | 3 | 334 | | 10000000 | 3 | 33334 | | 1000000000 | 4 | 3333334 | +------------+-----------------------+-------------------------+
What this code does
LOG(300, n)is the logarithm to base 300: how many times you dividenby 300 to reach 1. Rounded up, it is the number of tree levels, so the pages an index dive reads.- From 1,000 rows to 100 crore rows, the index lookup goes from 2 pages to 4. The full scan goes from 4 pages to over 33 lakh. That gap is the whole value of a B-tree.
- Real page counts depend on how wide the keys and rows are; the model only shows how slowly the height grows.
Heights stay tiny. If a page holds about 300 keys, two levels cover 300 × 300 = 90,000 rows, three levels cover 2.7 crore, and four levels cover over 800 crore. That is why the time of an index lookup is O(log n) and hardly grows when the table does.
The status counter Handler_read_key counts index dives. Reset the counters with FLUSH STATUS, run a query, and read them with SHOW SESSION STATUS.
Order of execution
Walk down the tree
Put the steps of an index dive in order.
Range scans on a B-tree
A range scan reads all keys between two values: one index dive to the first key, then a walk along the linked leaf pages until a key is past the end. It helps BETWEEN, < and >, and ORDER BY with LIMIT.
A range needs only one dive, then a walk along the leaves. The script below runs a range query and reads the counters that show one dive followed by next-key steps.
Range scan: keys from 40 to 75
Step 1 of 4
- found
- 40
Example 3 · One dive, then a walk along the leaves
SET SESSION cte_max_recursion_depth = 20000;
CREATE TABLE train_bookings ( booking_id INT PRIMARY KEY, pnr CHAR(10) NOT NULL, train_no INT NOT NULL, travel_date DATE NOT NULL, fare DECIMAL(8,2) NOT NULL);
INSERT INTO train_bookings (booking_id, pnr, train_no, travel_date, fare)WITH RECURSIVE seq AS ( SELECT 1 AS n UNION ALL SELECT n + 1 FROM seq WHERE n < 20000)SELECT n, CAST(4210000000 + n * 7919 AS CHAR), 12000 + n % 500, DATE '2026-01-01' + INTERVAL (n % 365) DAY, 200 + (n * 37) % 2800FROM seq;
FLUSH STATUS;
SELECT booking_id, pnr, fareFROM train_bookingsWHERE booking_id = 5000;
SHOW SESSION STATUS WHERE Variable_name IN ('Handler_read_key', 'Handler_read_next', 'Handler_read_rnd_next');
FLUSH STATUS;
SELECT booking_id, fareFROM train_bookingsWHERE booking_id BETWEEN 5000 AND 5009ORDER BY booking_id;
SHOW SESSION STATUS WHERE Variable_name IN ('Handler_read_key', 'Handler_read_next');
FLUSH STATUS;
SELECT booking_id, fareFROM train_bookingsORDER BY booking_id DESCLIMIT 3;
SHOW SESSION STATUS WHERE Variable_name IN ('Handler_read_last', 'Handler_read_prev');+------------+------------+--------+ | booking_id | pnr | fare | +------------+------------+--------+ | 5000 | 4249595000 | 400.00 | +------------+------------+--------+ +-----------------------+-------+ | Variable_name | Value | +-----------------------+-------+ | Handler_read_key | 1 | | Handler_read_next | 0 | | Handler_read_rnd_next | 0 | +-----------------------+-------+ +------------+--------+ | booking_id | fare | +------------+--------+ | 5000 | 400.00 | | 5001 | 437.00 | | 5002 | 474.00 | | 5003 | 511.00 | | 5004 | 548.00 | | 5005 | 585.00 | | 5006 | 622.00 | | 5007 | 659.00 | | 5008 | 696.00 | | 5009 | 733.00 | +------------+--------+ +-------------------+-------+ | Variable_name | Value | +-------------------+-------+ | Handler_read_key | 1 | | Handler_read_next | 10 | +-------------------+-------+ +------------+---------+ | booking_id | fare | +------------+---------+ | 20000 | 1000.00 | | 19999 | 963.00 | | 19998 | 926.00 | +------------+---------+ +-------------------+-------+ | Variable_name | Value | +-------------------+-------+ | Handler_read_last | 1 | | Handler_read_prev | 2 | +-------------------+-------+
What this code does
FLUSH STATUSsets this connection's counters back to 0. The single lookup showsHandler_read_key= 1: one dive from the root of the clustered index to booking 5000, and no scanning (Handler_read_rnd_next= 0).- The range needs one dive (
Handler_read_key= 1) to booking 5000, then 10 steps to the next key: 9 to reach 5009 and one more to see 5010 and stop. ORDER BY booking_id DESC LIMIT 3jumps to the last key (Handler_read_last= 1) and steps backwards twice (Handler_read_prev= 2). No sorting happens, because the tree is already sorted.
Because the keys are already in order, MySQL never sorts and never jumps around. The leaves are linked in both directions, so ORDER BY ... DESC can walk from the right end towards the left. The counters show it: Handler_read_next counts steps to the next key, Handler_read_prev steps backwards, and Handler_read_last counts jumps to the very last key.
The clustered primary key in InnoDB
A clustered index is an index whose leaf pages hold the full rows. In InnoDB the primary key is always the clustered index, so the table is a B-tree sorted by it. Every other index is a secondary index.
A lookup by primary key is the fastest there is, because the table is stored in that order. A lookup through a secondary index searches two trees, as the picture shows; the scripts below show the details.
Example 4 · The table is stored in primary key order
CREATE TABLE hostel_students ( roll_no INT PRIMARY KEY, name VARCHAR(40) NOT NULL, room INT NOT NULL);
-- Inserted out of order on purposeINSERT INTO hostel_students (roll_no, name, room) VALUES (2307, 'Neha', 214), (2301, 'Arjun', 101), (2305, 'Kiran', 118), (2302, 'Divya', 214);
-- No ORDER BY: never rely on this order in an appSELECT * FROM hostel_students;+---------+-------+------+ | roll_no | name | room | +---------+-------+------+ | 2301 | Arjun | 101 | | 2302 | Divya | 214 | | 2305 | Kiran | 118 | | 2307 | Neha | 214 | +---------+-------+------+
What this code does
- The rows were inserted as 2307, 2301, 2305, 2302, yet they come back sorted by
roll_no. InnoDB placed each row in the clustered index at its sorted position, and a plain scan reads the leaves left to right. - This order is a side effect, not a promise: with another plan, such as one that uses a secondary index, the order changes. The label says "Sample output" for that reason. Always write
ORDER BYwhen the order matters.
Example 5 · No primary key: InnoDB adds a hidden one
CREATE TABLE ipl_scores ( player VARCHAR(30) NOT NULL, runs INT NOT NULL);
SELECT i.NAME AS index_nameFROM information_schema.INNODB_INDEXES iJOIN information_schema.INNODB_TABLES t ON t.TABLE_ID = i.TABLE_IDWHERE t.NAME = CONCAT(DATABASE(), '/ipl_scores');
ALTER TABLE ipl_scores ADD COLUMN score_id INT AUTO_INCREMENT PRIMARY KEY FIRST;
SELECT i.NAME AS index_nameFROM information_schema.INNODB_INDEXES iJOIN information_schema.INNODB_TABLES t ON t.TABLE_ID = i.TABLE_IDWHERE t.NAME = CONCAT(DATABASE(), '/ipl_scores');+-----------------+ | index_name | +-----------------+ | GEN_CLUST_INDEX | +-----------------+ +------------+ | index_name | +------------+ | PRIMARY | +------------+
What this code does
information_schema.INNODB_INDEXESlists InnoDB's own indexes;INNODB_TABLESnames each table asdatabase/table. With no primary key, the only index isGEN_CLUST_INDEX, built on a hidden row id you can never use in a query.- After adding an
AUTO_INCREMENTprimary key, the clustered index isPRIMARY, on a column your queries can use. Giving every table a real primary key is the standard advice.
Example 6 · UUID versus AUTO_INCREMENT primary keys
SET SESSION cte_max_recursion_depth = 50000;
CREATE TABLE pay_int (id INT AUTO_INCREMENT PRIMARY KEY, amount INT NOT NULL);CREATE TABLE pay_uuid (id CHAR(36) PRIMARY KEY, amount INT NOT NULL);
INSERT INTO pay_int (amount)WITH RECURSIVE seq AS (SELECT 1 AS n UNION ALL SELECT n + 1 FROM seq WHERE n < 50000)SELECT n % 1000 FROM seq;
INSERT INTO pay_uuid (id, amount)WITH RECURSIVE seq AS (SELECT 1 AS n UNION ALL SELECT n + 1 FROM seq WHERE n < 50000)SELECT UUID(), n % 1000 FROM seq;
ANALYZE TABLE pay_int, pay_uuid;
SELECT table_name, stat_value AS leaf_pagesFROM mysql.innodb_index_statsWHERE database_name = DATABASE() AND table_name IN ('pay_int', 'pay_uuid') AND index_name = 'PRIMARY' AND stat_name = 'n_leaf_pages'ORDER BY table_name;+-------------------+---------+----------+----------+ | Table | Op | Msg_type | Msg_text | +-------------------+---------+----------+----------+ | practice.pay_int | analyze | status | OK | | practice.pay_uuid | analyze | status | OK | +-------------------+---------+----------+----------+ +------------+------------+ | table_name | leaf_pages | +------------+------------+ | pay_int | 88 | | pay_uuid | 197 | +------------+------------+
What this code does
- Both tables hold the same 50,000 UPI payments, yet the UUID table needs more than twice the leaf pages.
UUID()makes a random 36-character text id, so each key is 9 times wider than anINT. - Random keys also land in the middle of the tree: full pages split in two and stay partly empty. Increasing ids fill each page and move on. More pages mean more disk reads and a bigger buffer pool.
The leaf entries of a secondary index hold the indexed column plus the row's primary key. A lookup by a secondary index therefore searches two trees: first the secondary index to get the primary key, then the clustered index to get the row. Three things follow from this, and interviewers like all three:
- Every InnoDB table has a clustered index. With no primary key, InnoDB uses the first
UNIQUE NOT NULLindex, or else adds a hidden 6-byte row id and builds an index calledGEN_CLUST_INDEXon it. - A short primary key keeps every secondary index small.
- An increasing key such as
AUTO_INCREMENTadds rows at the right end of the tree. A random key such as a UUID inserts into the middle, splits pages and leaves them half full.
Next step
Check your understanding
12 quick questions