DATABASE
intermediate
B-Tree Indexes
Software Engineer path · lesson 53 of 99An interactive visualization showing how databases use B-Trees to retrieve data in O(log n) time without scanning the full table.
B-Tree Index vs Table Scan
Database Indexing
Ready
Target:
45Choose a target:
B-Tree Index
0
disk reads (O(log n))
Table Scan
0
rows scanned (O(n))
B-Tree Index Search
50
20
35
5
10
15
25
30
40
45
70
85
55
60
65
75
80
90
95
Disk Reads:0/ 3 max
Full Table Scan
5
10
15
20
25
30
35
40
45
50
55
60
65
70
75
80
85
90
95
Rows Scanned:0/ 19 total
Active Node
Found
Scanning
Checked
Look up a key
Sequence
Order an index lookup through a B-tree.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
5 pieces left to place
Test your knowledge
20 questions
Question 1 of 20
Score: 0
Which operation is highly efficient in a B+ Tree index but very slow using a Hash index?
The short version
A B-Tree index is like the index at the back of a textbook. Instead of reading every page (Full Table Scan) to find a topic, you jump straight to the exact page number.
In more depth
B-Tree Indexes
Databases store records on disk blocks. A B-Tree (and specifically B+ Tree) index helps locate these records instantly.
Core Properties
Balanced: All leaf nodes are at the same depth, guaranteeing O(log n) search times.
High Fan-out: Each node contains many keys and pointers, matching the size of a disk block to minimize I/O operations.
Range Scans: In a B+ Tree, leaf nodes are linked together in a linked list, allowing fast sequential access.
Interview Questions
Oracle
Amazon
Microsoft
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required