What is B-Tree Index?

A B-Tree index is a data structure used by relational databases to organize and retrieve data quickly while keeping the underlying storage balanced. Named after Rudolf Bayer and Edward McCreight who described it at Boeing in 1970 (often interpreted as 'balanced tree'), a B-Tree generalizes the binary search tree by allowing many children per node. Each node holds a sorted array of keys and pointers to child nodes or actual data rows.

In practice, a database index using a B-Tree stores key values in internal and leaf nodes. The internal nodes guide search decisions by comparing query keys against node keys. Every leaf node resides at the same depth, ensuring worst-case access time remains logarithmic with the number of rows. Unlike a binary tree, each B-Tree node can contain dozens or hundreds of keys, matching the block size of disk or flash storage. This design minimizes the number of reads or writes when inserting deleting or looking up rows, because each node access reads or writes one full block.

B-Tree indexes are the default index type in PostgreSQL MySQL Oracle and SQL Server for general purpose workloads. They excel at equality lookups (WHERE id = 42) and range scans (WHERE date BETWEEN '2024-01-01' AND '2024-01-31'). Data written to disk is always stored in sorted order across the leaf pages, which supports ordered output without sorting overhead. However, B-Trees introduce some write amplification and internal page splits when keys are inserted into full nodes, making them slightly less optimal for pure append workloads compared to LSM trees used by systems like LevelDB or RocksDB.