10.2 B Trees and B+ Trees. How they are useful in Databases

B-Trees and B+ Trees

B-trees and B+ trees are fundamental data structures used extensively in database systems. Understanding them requires familiarity with several foundational concepts:

• disk structure
• data storage
• indexing principles
• multi-level indexing
• M-way search trees.

Mastering these prerequisites enables a complete understanding of how B-trees evolve from simpler structures and why they are essential for database performance.

Disk Structure and Data Organization

A disk consists of concentric logical circles called tracks, numbered sequentially (track 0, track 1, track 2, and so on). The disk is also divided radially into sectors (sector 0, sector 1, sector 2, etc.). The intersection of a track and a sector defines a block, which represents the smallest addressable unit on the disk.

Any block can be located using its track number and sector number, forming the block address:

$$\text{Block address = (Track number, Sector number)}$$

A typical block size is 512 bytes, though this varies by manufacturer.

Within a block, individual bytes are addressed using an offset—the position relative to the block’s starting address. The first byte has offset 0, and the last byte in a 512-byte block has offset 511.

To access a specific byte on disk, three pieces of information are required: the track number, the sector number, and the offset within the block.

The disk platter is mounted on a spindle and accessed by a read/write head. Spinning the disk changes which sector is under the head, while moving the head arm changes which track is accessed. All disk operations—both reads and writes—occur in units of blocks, not individual bytes.

Data resides on disk, but programs execute in main memory (RAM). To access disk data, the system must first transfer it into main memory, where the program processes it. Any results are then written back to disk. This separation is fundamental: data structures organize data in main memory for direct program use, while database management systems (DBMS) organize data on disk for efficient storage and retrieval.

Database Storage and the Need for Indexing

Consider a database table with 100 records, where each record consists of multiple fields: employee ID (10 bytes), employee name (50 bytes), department (10 bytes), and additional fields, totaling 128 bytes per record. Given a block size of 512 bytes, each block can store ⌊512 ÷ 128⌋ = 4 records. Storing 100 records therefore requires ⌈100 ÷ 4⌉ = 25 blocks.

Searching for a specific record—such as finding the employee with ID 5 or name “Smith”—requires scanning through these blocks sequentially. In the worst case, all 25 blocks must be accessed. This number of block accesses directly determines query performance, and reducing it is critical for database efficiency.

Indexing provides a solution. An index stores each key value (such as employee ID) along with a record pointer that indicates where the corresponding record resides on disk:

Where do you store index? We’ll store index also in the disk, in another block:

How much space does the index take up? For the 100-record table, the index contains 100 entries. Each entry consists of a 10-byte key and a 6-byte record pointer, totaling 16 bytes. Since 512 ÷ 16 = 32 entries fit in one block, the entire index occupies ⌈100 ÷ 32⌉ ≈ 4 blocks. So, when searching for a record using an index, the system first searches the index (at most 4 block accesses), identifies the target record’s location, and then accesses that specific block (1 additional access). The total is 5 block accesses instead of 25—a significant improvement.

Multi-Level Indexing

As the database grows, the index itself becomes large. For a table with 1,000 records, the index requires approximately 40 blocks. Searching 40 blocks is still substantial. This motivates multi-level indexing: creating an index on the index.

The second-level index is sparse, meaning it does not index every entry in the first-level index. Instead, it indexes blocks of entries. For an index block containing 32 entries, the second-level index has one entry pointing to the starting key of that block:

If the first-level index occupies 40 blocks and each second-level index block can reference 32 first-level blocks, the second-level index requires only ⌈40 ÷ 32⌉ = 2 blocks.

Searching now involves accessing 2 blocks at the second level, 1 block at the first level, and 1 data block—totaling 4 block accesses.

Additional levels can be added as needed: each higher level indexes the blocks of the level below, forming a hierarchical tree structure. This tree grows upward as more levels are added:

The key requirement of Multi-Level Indexing is self-management: As records are inserted or deleted, the index structure must adjust automatically, adding or removing levels as necessary without manual intervention. This self-managing multi-level index is precisely what B-trees and B+ trees provide.

M-Way Search Trees

Before examining B-trees, consider the binary search tree (BST), where each node contains one key and has at most two children (that’s why it’s called binary tree). Keys smaller than the node’s key reside in the left subtree, and larger keys reside in the right subtree. Searching proceeds by comparing the target key with the current node and traversing left or right accordingly.

An M-way search tree generalizes this concept. Each node can contain up to M−1 keys and have up to M children. Keys within a node are stored in sorted order. For a node with keys k₁ and k₂ (where k₁ < k₂), the first child points to keys less than k₁, the second child points to keys between k₁ and k₂, and the third child points to keys greater than k₂.

For example, a node containing keys 20 and 50 has three children: one for keys less than 20, one for keys between 20 and 50, and one for keys greater than 50. Searching in an M-way search tree follows the same principle as a BST but involves comparing against multiple keys per node to determine which child to follow.

A binary search tree is simply a 2-way search tree. M-way search trees extend this to arbitrary degrees, allowing nodes with many keys and children.

Node Structure for Indexing of M-Way Search Tree

After presenting a diagrammatic representation of an M-way search tree, we now describe the structure of a node from a data-structure perspective.

2-Way Search Tree (Binary Search Tree)

Let’s first start with 2-way search tree (Binary Search Tree). Each node contains:

• Child pointer to a children
• Key
• Child pointer to another children

4-Way Search Tree

Now, let’s consider a 4-way search tree (each node can have 4 children and 3 keys). Each node contains:

• Child pointer 1
• Key 1
• Child pointer 2
• Key 2
• Child pointer 3
• Key 3
• Child pointer 4

4-Way Search Tree for Indexing

To use M-way search trees for indexing, the node structure must include both child pointers and record pointers. For a 4-way search tree (degree M = 4), each node contains:

• Child pointer 1
• Key 1
• Record pointer 1
• Child pointer 2
• Key 2
• Record pointer 2
• Child pointer 3
• Key 3
• Record pointer 3
• Child pointer 4

This alternating pattern of child pointers and keys allows each key to reference both its position in the tree structure (via child pointers) and its corresponding data record (via record pointers).

Limitations of M-Way Search Trees

M-way search trees have a critical flaw: uncontrolled growth. Insertion follows no strict rules, so the tree can degenerate into a linear structure. For instance, inserting keys 10, 20, 30 into a 10-way search tree might create a single node containing all three keys, or it might create a chain of nodes with one key each. In the worst case, a tree with n nodes has height n, reducing search efficiency to linear time—no better than scanning the data sequentially.

The problem is the absence of guidelines or rules governing tree construction. B-trees solve this by imposing strict constraints on M-way search trees.

B-Trees: Controlled M-Way Search Trees

A B-tree is an M-way search tree with mandatory rules ensuring balanced growth and efficient searching:

1. Every node must be at least half full. Each node must have at least ⌈M/2⌉ children (using the ceiling function). For a tree of degree 10, each node must have at least 5 children, meaning at least 4 keys.
2. The root is an exception. The root can have a minimum of 2 children (and thus just 1 key), allowing the tree to start small.
3. All leaf nodes must be at the same level. This ensures the tree remains balanced, guaranteeing logarithmic search time.
4. Creation proceeds bottom-up. Unlike typical trees built top-down, B-trees grow upward from the leaves, automatically creating higher levels as needed.

Insertion and Splitting

To illustrate B-tree construction, consider creating a B-tree of degree 4 (each node holds up to 3 keys and 4 children) by inserting keys: 10, 20, 40, 50, 60, 70, 80, 30, 35, 5, 15.

Insert 10, 20, 40: The first node contains [10, 20, 40].

Insert 50: The node is full. Split it: place [10, 20] in one node, [50] in another, and promote 40 to become the root. The tree now has a root [40] with two children [10, 20] and [50].

Insert 60, 70: Add to the right child: [50, 60, 70].

Insert 80: The right child is full. Split it: [50, 60] in one node, [80] in another, promote 70 to the root. The root becomes [40, 70] with three children: [10, 20], [50, 60], and [80].

Insert 30: Add to the left child: [10, 20, 30].

Insert 35: The left child is full. Split it: [10, 20] and [35] in two nodes, promote 30 to the root. The root becomes [30, 40, 70]. However, if further insertions cause the root itself to overflow, it too must split, creating a new root at a higher level.

Insert 5: Add to [10, 20]: becomes [5, 10, 20].

Insert 15: The node [5, 10, 20] is full. Split it: [5, 10] and [20], promote 15 to the parent (actually, you could promote 10 instead of 15: it would be OK, it’s a personal choice). If the parent is full, split it and promote a key upward. This process continues recursively, potentially increasing the tree’s height.

This bottom-up splitting mechanism ensures that all leaf nodes remain at the same level and that each node maintains at least half capacity, guaranteeing balanced growth.

B-Tree Node Structure for Databases

In database applications, each B-tree node contains:z

• Keys: The indexed values (e.g., employee IDs).
• Child pointers (block pointers): References to child nodes in the tree.
• Record pointers: Direct pointers to the actual data records stored in data blocks.

This structure allows the B-tree to serve as a multi-level index. Internal nodes guide the search, while every key—whether in an internal node or a leaf—has a record pointer enabling direct access to the corresponding data.

B+ Trees: Optimized B-Trees for Databases

A B+ tree refines the B-tree structure to better suit database indexing:

1. Record pointers exist only at the leaf level. Internal nodes contain keys for navigation but do not point to data records.
2. All keys appear in the leaf nodes. Internal nodes may contain copies of keys from the leaves, but every actual key value resides in a leaf.
3. Leaf nodes are linked. All leaf nodes form a linked list, enabling efficient sequential access and range queries.

Example Transformation

Consider the B-tree from the previous example. To convert it to a B+ tree:

• Remove record pointers from internal nodes.
• Ensure every key in internal nodes also appears in a leaf. For instance, if 15 and 30 are internal keys, they must also appear in the appropriate leaf nodes.
• Connect all leaf nodes with pointers: [5, 10] → [15, 20] → [30, 35] → [40, 50, 60] → [70, 80], forming a dense index at the leaf level.

Advantages of B+ Trees

Dense vs. Sparse Indexing: The leaf level forms a dense index containing all keys and record pointers, supporting efficient exact-match and range queries. The internal levels form a sparse index that guides searches to the correct leaf.

Sequential Access: The linked leaf nodes allow traversing all keys in sorted order without revisiting internal nodes, which is invaluable for range queries and full-table scans.

Simplified Internal Nodes: By removing record pointers from internal nodes, each internal node can hold more keys, reducing the tree’s height and further improving search performance.

Summary

B-trees and B+ trees provide self-managing, balanced multi-level indexes essential for database systems. Starting from basic disk organization and indexing principles, we’ve seen how uncontrolled M-way search trees fail to scale efficiently. B-trees impose structural rules—minimum node capacity, balanced height, and bottom-up growth—that guarantee logarithmic search times. B+ trees refine this further by concentrating all data references in a linked leaf level, optimizing both point queries and range scans. Understanding these structures requires tracing their evolution from simpler concepts, revealing why they remain the backbone of modern database indexing.