How B-tree Indexes Work

Lesson 10.5 · Reading time: ~11 min · Practice tasks ↓

This lesson explains in detail how B-tree indexes work in SQL at the physical and logical level. You will learn what nodes make up the structure, how the database traverses the tree, and why this approach speeds up filtering and sorting. We will look at practical examples on Sakila tables and reinforce key usage rules. By the end of the lesson, you will better understand when a B-tree index actually accelerates queries.

In the previous lessons, you learned how to create indexes and how to check in the execution plan that a query uses them. Now let's understand how an index is organized internally and why it speeds up search.

Understanding B-tree will help you see when an index truly works and when it cannot be used. This knowledge will be useful when optimizing slow queries.

What Is a B-tree Index

A B-tree index is like a table of contents in a book. Instead of reading all pages in order, you open the table of contents, find the chapter you need, and go there directly.

A B-tree has three levels:

• root node - the starting point of the search, like the cover of a table of contents;
• intermediate nodes - suggest which direction to go next;
• leaf nodes - contain the values you need and links to table rows.

The entire structure is sorted, so the database can quickly choose the right direction at each level.

Here's what it looks like:

                    [ ROOT ]
                   /   |   \
                  /    |    \
            [NODE A] [NODE B] [NODE C]
            / |  \    / | \    / | \
           /  |   \  /  |  \  /  |  \
         [L1][L2][L3][L4][L5][L6][L7][L8]

Each node contains values that help select the next node. Leaf nodes (L1–L8) contain the data you need.

How Search by B-tree Works

When you search for WHERE last_name = 'SMITH', the database:

1. starts from the root node;
2. selects the branch where names beginning with 'S' might be;
3. descends, refining the search at each level;
4. finds the name you need in a leaf node.

Thanks to this algorithm, search is very fast - even in a table with millions of rows, you only need to check a few levels.

What Operations Does B-tree Accelerate Best

Equality (=)

B-tree is well suited for exact value searches.

SELECT
   customer_id,
   first_name,
   last_name
FROM customer
WHERE last_name = 'SMITH';

Ranges (>, <, BETWEEN)

Because the keys are sorted, B-tree is efficient for range conditions.

SELECT
   payment_id,
   amount,
   payment_date
FROM payment
WHERE payment_date >= '2005-07-01'
  AND payment_date < '2005-08-01';

Sorting (ORDER BY)

If the sort order matches the index, the database can often avoid expensive separate sorting.

SELECT
   payment_id,
   customer_id,
   payment_date
FROM payment
WHERE customer_id = 10
ORDER BY payment_date;

Example of a Composite B-tree Index

Let's create an index for a common filtering and sorting pattern:

CREATE INDEX idx_payment_customer_date
ON payment (customer_id, payment_date);

Let's check the plan:

EXPLAIN
SELECT
   payment_id,
   customer_id,
   payment_date,
   amount
FROM payment
WHERE customer_id = 10
  AND payment_date >= '2005-07-01'
ORDER BY payment_date;

Result: typically the database uses the index for filtering by customer_id and the range payment_date, as well as for ordered reading.

Leftmost Prefix Rule for Composite Indexes

If an index is created as (customer_id, payment_date), the database uses it best if the condition first filters by customer_id.

Works well:

WHERE customer_id = 10

Works well:

WHERE customer_id = 10 AND payment_date >= '2005-01-01'

Works poorly:

WHERE payment_date >= '2005-01-01'

This rule is called the "leftmost prefix": the index works best when you use conditions from left to right.

When an Index Doesn't Help

An index is not used if:

• you apply a function to a column: WHERE YEAR(payment_date) = 2005 - the index doesn't work;
• you use a mask at the beginning: WHERE name LIKE '%SMITH' - the index won't help;
• the condition is too general and returns many rows - the index may be slower than reading the entire table.

Bad (function prevents index use):

SELECT payment_id, payment_date
FROM payment
WHERE YEAR(payment_date) = 2005;

Good (index can work):

SELECT payment_id, payment_date
FROM payment
WHERE payment_date >= '2005-01-01'
  AND payment_date < '2006-01-01';

Practical Recommendations

• Index fields that frequently appear in WHERE, JOIN, ORDER BY.
• For composite indexes, put the most important column for filtering first.
• Check actual index usage through EXPLAIN.
• Don't create redundant indexes: they increase the cost of writes.

Key takeaways from this lesson:

• B-tree is a balanced structure that accelerates key search.
• The main strength of B-tree: equality, ranges, and sorting by index order.
• Composite indexes follow the leftmost prefix rule.
• An inappropriate condition form can deprive a query of index benefits.
• EXPLAIN helps you understand whether B-tree is used in the actual execution plan.

Frequently Asked Questions

What does the B in B-tree stand for?

It is usually read as "balanced": every leaf is the same distance from the root, so any lookup takes the same number of steps. Rudolf Bayer and Edward McCreight, who described the structure in 1972, never explained the letter. Most databases actually use the B+tree variant, where the leaves are linked into a list, which makes range scans fast.

What is the difference between a B-tree index and a hash index?

A hash index finds exact matches (=) and nothing else. A B-tree also handles ranges (>, <, BETWEEN), ORDER BY and prefix searches like LIKE 'SM%', because its keys are sorted. That is why B-tree is the default index type in MySQL (InnoDB) and PostgreSQL.

How deep is a B-tree index?

Usually three or four levels, even for millions of rows. Each node is a disk page (16 KB in InnoDB, 8 KB in PostgreSQL) that holds hundreds of keys, so every level multiplies the number of reachable rows by hundreds. Finding a row therefore takes only a few page reads.

Interview Questions

Why is a B-tree index usually faster than a full scan?

Because the database traverses the tree along branches and finds the needed range in a logarithmic number of steps, instead of scanning all table rows.

What is the leftmost prefix rule for a composite index?

This rule means that the optimizer uses the index best when starting from the first column of the key and proceeding in order.

How do you check in practice that a B-tree index is being used?

You run EXPLAIN and look at the access type, chosen key, and expected number of rows at each execution stage.