Understanding B-Trees and Database Indexes

B-Trees are a fundamental data structure behind database indexes

By Amal V S, Backend & AI Systems Architect · Fri Mar 06 2026

Modern databases handle massive amounts of data. To retrieve data quickly, they rely on indexes, and one of the most common structures used for indexes is the B-Tree.

What is a B-Tree?

A B-Tree is a tree-based data structure used to store key–value pairs in a sorted way. Instead of storing everything in one list, the data is organized into nodes that form a tree structure. This allows databases to quickly search, insert, and update data

The “B” in B-Tree stands for balanced, meaning the tree keeps its height balanced so that operations take roughly the same time regardless of data size.

When searching for a value, the database starts at the root and moves down the tree until it finds the correct node.

Why Databases Use B-Trees

Databases such as MySQL, PostgreSQL, and MongoDB commonly use B-Trees because they work well with large datasets stored on disk.

Key benefits:

  • Fast lookups (O(log n) complexity)

  • Efficient insertions and deletions

  • Works well with disk storage

  • Supports range queries (e.g., WHERE age BETWEEN 20 AND 30)

Each node in a B-Tree can be sized to match a disk page, which reduces disk reads and improves performance.

B+ Trees in Databases

Most databases actually use a variation called the B+ Tree.

Main differences:

  • Leaf nodes store the actual data

  • Internal nodes store only keys and pointers

  • Leaf nodes are connected like a linked list

Because of this structure:

  • The tree stays shallow

  • Range queries become very efficient

This is why storage engines like MySQL InnoDB rely heavily on B+ Trees for indexes

Example: Index in a Database

Consider a table:

CREATE TABLE user (
  user_id BIGINT PRIMARY KEY,
  username VARCHAR(255),
  email VARCHAR(255)
);

CREATE INDEX email_index ON user(email);

Here the database creates:

  1. Primary key B+Tree → keyed by user_id

  2. Secondary index B+Tree → keyed by email

When querying:

SELECT username FROM user WHERE email='x@example.com';

The database:

  1. Searches the email index tree

  2. Gets the matching user_id

  3. Uses that to fetch the row from the primary key tree

Choosing the Right Primary Key

The choice of primary key affects how the B-Tree grows.

Sequential keys (auto-increment integers)

  • Inserts happen at the end of the tree

  • Better disk locality

  • Faster writes

Random keys (UUIDv4)

  • Inserts occur in random nodes

  • More page splits

  • Worse performance

Because of this, many databases recommend sequential IDs for primary keys

Conclusion

B-Trees are a fundamental data structure behind database indexes. They help databases:

  • Find data quickly

  • Handle large datasets efficiently

  • Support range queries and sorting

Most modern databases use B+ Trees, a variant optimized for disk storage and high-performance queries.

Understanding B-Trees helps developers design better indexes and faster databases.