B-Tree Index

A B-tree index is a balanced, ordered database structure that helps locate rows efficiently without scanning the entire table. It is especially useful for equality lookups, range queries, and retrieving data in index order.

A B-tree index stores indexed values in sorted order and organizes them into a hierarchy of nodes. The tree remains balanced, so searches follow a path from the root toward the relevant leaf rather than examining every row.

Database systems typically store B-tree index pages separately from table data. Internal nodes guide the search, while leaf nodes contain indexed values and references to the corresponding table rows; leaf organization also makes ordered traversal practical.

For example, an index on `age` can efficiently find rows where `age = 30`, `age >= 30`, or `age BETWEEN 20 AND 30`. Because the values are ordered, a database can find the starting position and then scan adjacent index entries for a range.

B-tree indexes can also help with sorting when the requested ordering matches the index's ordering. The database optimizer decides whether using the index is cheaper than another access method, so creating an index does not guarantee that every query will use it.

Indexes improve read performance at a cost: inserts, updates, and deletes may require index maintenance, and indexes consume storage. Good index design therefore considers both query patterns and write workload.

Key points

• Keeps indexed values ordered in a balanced tree structure.
• Supports efficient equality and range lookups.
• Leaf-level ordering can support ordered scans and some `ORDER BY` operations.
• Indexes consume storage and add maintenance work to writes.
• The query optimizer chooses whether an index is useful for a particular query.

Interview questions

What are the costs of adding an index?

An index requires additional disk or memory resources and must be maintained when indexed data changes. Inserts, deletes, and updates can therefore become more expensive. The benefit is faster access for queries that can effectively use the index.

How does a B-tree index differ from a hash index?

A B-tree keeps keys ordered, so it can efficiently support equality predicates as well as ranges and ordered traversal. A hash index maps keys through a hash function and is primarily intended for equality lookups. Therefore, ordering-dependent operations generally favor a B-tree-style structure.

Why doesn't creating an index guarantee that the database will use it?

The optimizer compares possible execution strategies using estimates such as selectivity, available indexes, and estimated work. If an index would require many random row fetches or a large portion of the table matches, a scan can be cheaper. The optimizer's choice therefore depends on the particular query and data distribution.

How can an index help an `ORDER BY` query?

If the index's key order is compatible with the requested ordering, the database may read index entries in that order instead of performing a separate sort. Whether this is beneficial depends on the query, predicates, index definition, and how many table rows must ultimately be fetched. A composite index can be particularly useful when its leading columns align with filtering and ordering requirements.

Why can a B-tree index support a range query efficiently?

The indexed keys are kept in sorted order. The database can first locate the beginning of the requested range and then traverse subsequent index entries in order. This avoids repeatedly searching the entire table for each matching value.

What problem does a B-tree index solve?

It provides a way to find rows without checking every row in the table. The indexed values are organized in sorted, balanced levels, so the database can navigate toward the desired value efficiently. Because the values remain ordered, the same structure can also support ranges and ordered access.