Introduction

A B+ Tree is a type of data structure used in computer science for efficient

data storage and retrieval. Unlike B Tree, the B+ Tree stores all values in the
leaf nodes and use internal nodes only for indexing. This structure ensures
fast data access, making it ideal for database indexing and file systems.

Let’s learn everything about B Plus Tree in data structure.

What is B+ Tree?

A B+ Tree is a type of data structure used in computer science to store and

organize data. It is a special kind of tree where all the values (data) are
stored in the leaf nodes, and the internal nodes are used only for indexing
(like a table of contents). This structure helps in quickly finding, inserting,
and deleting data.

In a B Plus Tree, the leaf nodes are linked together like a linked list, which
makes it easy to find a range of values quickly.

For example, if you want to find all the values between 10 and 20, you can
quickly go to the starting point and then follow the links to get all the values
in that range.

Properties of B+ Tree

 Balanced Tree Structure: B+ Trees are balanced, meaning all leaf

nodes are at the same level.
  Leaf Nodes Store All Values: All actual data values are stored in the
leaf nodes.

 Internal Nodes for Indexing: Internal nodes contain only keys and
pointers to child nodes.

 Linked List of Leaf Nodes: Leaf nodes are linked together in a linked
list.

 Order of the Tree: The order (m) of a B+ Tree defines the maximum
number of children each internal node can have.

⌈m/2⌉.
 Minimum Degree: The minimum degree (t) of a B+ Tree is defined as

 Efficient Disk Read/Write: B+ Trees are designed to minimize disk

I/O operations.

Nodes in B+ Tree

In a B+ Tree, nodes are of two main types: internal nodes and leaf nodes.

 Internal Nodes

Internal nodes are used for indexing and routing purposes within the tree.
They do not store actual data values but rather keys that help in navigating
the tree.

 Leaf Nodes

Leaf nodes store the actual data values. All the data in a B+ Tree is
contained within the leaf nodes.

Order of B+ Tree

The order of a B+ Tree, often denoted as m, is a fundamental property that

determines the tree's structure and balance. The order of a B+ Tree specifies
the maximum number of children that any node in the tree can have. Here’s
a detailed explanation of what the order of a B+ Tree means and its
implications:

Order m:

The order of a B+ Tree is the maximum number of children that any internal
node can have.

For a B+ Tree of order m:

  Each internal node can have at most m children.

 Each internal node (except the root) must have at least (m/2) children.

 Each internal node must have between (m/2) - 1 and m - 1 keys.

 Each leaf node must have between (m/2) and m values.

Operations on B+ Trees

B+ Trees support various operations such as insertion, deletion, and

searching. These operations ensure that the tree remains balanced and
efficient for data retrieval and modification.

1. Insertion

Algorithm:

1. Start from the root and find the appropriate leaf node where the key
should be inserted.

2. Insert the key in the leaf node in sorted order.

3. Split the Node (if necessary):

 If the leaf node has more than m−1 keys after insertion, split the node
into two.

 Promote the middle key to the parent node.

 If the parent node also overflows, repeat the splitting process up to the
root.

4. Ensure that leaf nodes are linked correctly after any split.

Example:

Insert keys 10, 20, 5, 6, 12, 30, 7, 17 in a B+ Tree of order 4.

 Insert 10:

[10]

 Insert 20:

[10, 20]

 Insert 5:

[5, 10, 20]

  Insert 6 (causes split):

Before split: [5, 6, 10, 20]

After split:

 Internal: [10]

 Leaf: [5, 6] [10, 20]

 Insert 12:

Internal: [10]

Leaf: [5, 6] [10, 12, 20]

 Insert 30:

Internal: [10]

Leaf: [5, 6] [10, 12, 20, 30]

 Insert 7 (causes split):

Before split: [5, 6, 7] [10, 12, 20, 30]

After split:

Internal: [10, 20]

Leaf: [5, 6, 7] [10, 12] [20, 30]

 Insert 17:

Internal: [10, 20]

Leaf: [5, 6, 7] [10, 12, 17] [20, 30]

2. Deletion

Algorithm:

1. Start from the root and find the leaf node containing the key.

2. Remove the key from the leaf node.

3. Merge or Redistribute Nodes (if necessary):

 If the leaf node has fewer than ⌈m/2⌉ keys after deletion, merge or
redistribute nodes.
  If merging, remove the corresponding key from the parent and merge
nodes.

 If the parent node underflows, repeat the process up to the root.

Example:

Delete key 12 from the B+ Tree after the previous insertions.

 Find 12:

Internal: [10, 20]

Leaf: [5, 6, 7] [10, 12, 17] [20, 30]

 Delete 12:

Internal: [10, 20]

Leaf: [5, 6, 7] [10, 17] [20, 30]

3. Searching

Algorithm:

1. Begin the search from the root node.

2. Compare the key with the keys in the current node:

 If the key is less than a key in the node, follow the corresponding child
pointer.

 If the key is greater, move to the next key or child pointer.

3. Continue this process until you reach the leaf node.

4. Look for the key in the leaf node.

Example:

Search for key 17 in the B+ Tree.

 Start at Root:

Internal: [10, 20]

Leaf: [5, 6, 7] [10, 17] [20, 30]

 Traverse:

Key 17 is greater than 10 but less than 20, move to the second child.
  Find 17 in Leaf Node:

Leaf: [10, 17]

B+ Tree Traversal Methods

Traversal methods for B+ Trees involve visiting all the nodes in the tree in a
specific order. The main traversal methods are in-order traversal and range
queries. Each method serves different purposes and has its own algorithm.

1. In-order Traversal

In-order traversal in a B+ Tree involves visiting all the leaf nodes in sorted
order. This method is particularly efficient because B+ Trees store all values
in the leaf nodes, and these nodes are linked together in a linked list.

Algorithm:

1. Begin the traversal from the leftmost leaf node.

2. Visit each key in the current leaf node.

3. Follow the pointer to the next leaf node and repeat the process.

4. Continue until you reach the end of the leaf nodes.

Example:

Consider the following B+ Tree:

In-order Traversal Steps:

 1. Start at the leftmost leaf node: [5, 10, 15]

2. Visit keys in the current leaf node: 5, 10, 15

3. Move to the next leaf node: [25, 30, 35]

4. Visit keys: 25, 30, 35

5. Move to the next leaf node: [45, 50, 55]

6. Visit keys: 45, 50, 55

In-order Traversal Result: 5, 10, 15, 25, 30, 35, 45, 50, 55

2. Range Queries

Range queries in a B+ Tree involve finding all the keys within a specified
range. This method takes advantage of the linked list structure of the leaf
nodes, making it efficient for range searches.

Algorithm:

1. Start from the root and find the leaf node containing the starting key of
the range.

2. Visit each key in the current leaf node that falls within the range.

3. Follow the pointer to the next leaf node and repeat the process until all
keys in the range are found.

4. Continue until you reach the end of the range.

Example:

Consider the following B+ Tree and a range query for keys between 15 and
35:
Range Query Steps:

1. Find the starting leaf node: [5, 10, 15]

2. Visit keys in the current leaf node: 15

3. Move to the next leaf node: [25, 30, 35]

4. Visit keys: 25, 30, 35

5. Range query result: 15, 25, 30, 35