Databases · interactive
B-tree indexes
Find one row without an index and the database reads every page of the table. A B-tree keeps the keys sorted in a shallow tree, so it reads one page per level. Find id 44 both ways.
Index on id · one box = one page
- 2956
- 1120
- 3847
- 6574
- 258
- 111417
- 202326
- 293235
- 384144
- 475053
- 565962
- 656871
- 747780
The table, as stored (no index): 9 pages
- 41874
- 23592
- 683514
- 50775
- 296220
- 441171
- 563280
- 174726
- 653853
Page reads with the index1
Page reads with a full scan9
Start at the root. 29 ≤ 44 < 56: go middle. 1 page read so far.
Find id
1 The root holds a few keys that split the whole range of ids. One page read.
root keys: 29, 56
2 3 4
In production
Tools and technologies
B-trees are the default index in almost every relational database.
Not tied to one language — use these names when you search docs or design a system.
- PostgreSQL indexesSoftware
CREATE INDEX makes a B-tree unless you ask for another type.
Documentation ↗ - MySQL InnoDBSoftware
Tables are stored as B+ trees ordered by the primary key.
Official site ↗ - SQLiteSoftware
Every table and index is a B-tree in one file.
Official site ↗ - EXPLAINStandard
Shows whether a query used an index scan or a sequential scan.
Documentation ↗