B-Trees and B+ Trees

4
0

Introduction

A database index must locate records efficiently even when a table contains millions of rows. A search structure that grows too tall can require many page accesses before reaching the required record.

B-Trees and B+ Trees address this problem through balanced structures with many children per node. Their organization supports efficient searches while adapting as records are inserted and deleted.

Why Databases Use Multiway Trees

A binary search tree has at most two children per node. B-Trees and B+ Trees are multiway search trees, meaning a node can have many children.

Their nodes are commonly designed around database pages. A page can hold several keys and child pointers, allowing each node to cover a large portion of the indexed data.

The number of children a node has is its fan-out. High fan-out keeps the tree shallow, reducing the number of pages needed along a search path.

Both structures remain balanced: all leaf nodes are at the same depth.

What Is a B-Tree?

A B-Tree stores sorted search keys across internal nodes and leaf nodes. In the classic organization, keys at either level can have associated records or record references.

Consider this simplified tree:

What is B-Tree ?

What is B-Tree ?

The root divides the search space:

  • Keys below 30 belong to the left subtree.

  • Keys between 30 and 60 belong to the middle subtree.

  • Keys above 60 belong to the right subtree.

To find 50, compare it with the root keys, follow the middle child, and locate it in [40 | 50].

A search for 30 can finish at the root because a B-Tree may store the associated record reference there.

What Is a B+ Tree?

A B+ Tree uses internal nodes to guide searches. Its leaf level contains the data entries: search keys together with records or record references.

Internal keys act as separators and may also appear at the leaf level.

What is B+ Tree ?

What is B+ Tree ?

In this illustrative layout, values equal to a separator follow the child to its right.

To find 30:

  1. Read the root separator.

  2. Follow the middle child.

  3. Locate the data entry for 30 in the leaf.

Point lookups continue to a leaf, even when the search key appears in an internal node.

Leaf nodes are linked in key order. These links support moving through consecutive entries without restarting a search from the root.

B-Tree vs B+ Tree

Feature

B-Tree

B+ Tree

Data-entry location

Internal and leaf nodes

Leaf nodes

Internal-node role

Store keys and associated data entries

Guide searches using separator keys

Search termination

May finish at an internal node

Continues to a leaf

Leaf links

Not a defining requirement

Typically linked in key order

Range traversal

Requires navigating the tree

Can continue through linked leaves

Because B+ Tree internal nodes do not store the associated record payload, they can often fit more separator keys and child pointers into a page. The actual capacity depends on key sizes and implementation.

Why B+ Trees Help Range Queries

Suppose a query needs keys from 40 through 70.

Using the B+ Tree above:

  1. Search for the first qualifying entry, 40.

  2. Read 40 and 50 from the current leaf.

  3. Follow the leaf link.

  4. Read 60 and 70.

  5. Stop before 80, which exceeds the range.

The qualifying keys are:

40, 50, 60, 70

A B-Tree also supports range queries. The B+ Tree’s linked leaf level makes consecutive traversal especially convenient.

However, ordered index traversal does not guarantee the order of a SQL query’s output. Use ORDER BY when output order matters.

Insertion and Deletion

Both trees maintain sorted keys, capacity rules, and balance as entries change.

During insertion, the database locates the appropriate node and adds the entry. If the node overflows, it splits. This can require changes in the parent and may propagate upward. Splitting the root creates a new root and increases the height.

During deletion, the database removes the entry. If a node becomes too empty, entries may be redistributed from a sibling or nodes may be merged. Parent separators are adjusted as needed.

In a B+ Tree, a leaf split typically copies a separator into the parent while retaining the data entry at the leaf level.

Summary

B-Trees and B+ Trees use balanced, multiway branching to keep search paths short. Their main difference is where data entries are stored: B-Trees can store them throughout the tree, while B+ Trees keep them at the leaves.

B+ Trees also connect their leaves in key order, supporting efficient range traversal. Both structures preserve their organization through splits, redistribution, and merges as data changes.

CS Core

Read Similar Blogs

Comments0