Course contentsShow
← Computer Science
Lesson 1676 of 2,87238. Database Transactions and IndexingFree lesson

B-Tree Index Overview

What B-Tree indexes are, why databases use them, and how they differ from in-memory BSTs.

B-Tree Index Overview

You'll learn what B-Tree indexes are, why databases rely on them, and how they differ from simpler tree structures.

What Is a B-Tree Index?

A B-Tree index is a self-balancing tree structure that databases use to organize and quickly locate data on disk. Unlike the binary search trees (BSTs) you might've seen in algorithms courses, B-Trees are designed specifically for systems that read and write large blocks of data to disk, not just RAM.

Think of a B-Tree like a multi-level index in a phone book. Each page (node) contains many names and pointers to other pages, not just one or two. This means you can skip huge sections of the book with just a few page turns, minimizing how many times you need to flip pages (disk reads).

Why Databases Use B-Trees

Disk I/O is thousands of times slower than memory access. A database query that reads from disk 100 times will be painfully slow. B-Trees minimize disk reads by:

  • Storing many keys per node (often hundreds), matching the size of disk blocks
  • Keeping the tree shallow, so you traverse fewer levels
  • Staying balanced automatically, ensuring consistent performance even after many inserts and deletes

How They Differ from In-Memory BSTs

FeatureIn-Memory BSTB-Tree Index
Keys per node1Hundreds
Optimized forRAM accessDisk I/O
HeightOften tallerVery shallow
Node sizeTinyMatches disk block

A BST might require 20 hops to find a record; a B-Tree might need only 3–4 disk reads for millions of records.

Key Takeaway: B-Tree indexes are disk-optimized structures that dramatically speed up database queries by minimizing expensive disk I/O operations through wide, shallow trees.