Open In App

Introduction of B+ Tree

Last Updated : 08 Mar, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

B + Tree is a variation of the B-tree data structure. In a B + tree, data pointers are stored only at the leaf nodes of the tree. In a B+ tree structure of a leaf node differs from the structure of internal nodes. The leaf nodes have an entry for every value of the search field, along with a data pointer to the record (or to the block that contains this record). The leaf nodes of the B+ tree are linked together to provide ordered access to the search field to the records. Internal nodes of a B+ tree are used to guide the search. Some search field values from the leaf nodes are repeated in the internal nodes of the B+ tree.

Features of B+ Trees

  • Balanced: B+ Trees are self-balancing, which means that as data is added or removed from the tree, it automatically adjusts itself to maintain a balanced structure. This ensures that the search time remains relatively constant, regardless of the size of the tree.
  • Multi-level: B+ Trees are multi-level data structures, with a root node at the top and one or more levels of internal nodes below it. The leaf nodes at the bottom level contain the actual data.
  • Ordered: B+ Trees maintain the order of the keys in the tree, which makes it easy to perform range queries and other operations that require sorted data.
  • Fan-out: B+ Trees have a high fan-out, which means that each node can have many child nodes. This reduces the height of the tree and increases the efficiency of searching and indexing operations.
  • Cache-friendly: B+ Trees are designed to be cache-friendly, which means that they can take advantage of the caching mechanisms in modern computer architectures to improve performance.
  • Disk-oriented: B+ Trees are often used for disk-based storage systems because they are efficient at storing and retrieving data from disk.

Why Use B+ Tree?

  • B+ Trees are the best choice for storage systems with sluggish data access because they minimize I/O operations while facilitating efficient disc access.
  • B+ Trees are a good choice for database systems and applications needing quick data retrieval because of their balanced structure, which guarantees predictable performance for a variety of activities and facilitates effective range-based queries.

Difference Between B+ Tree and B Tree

Some differences between B+ Tree and B Tree are stated below.

Parameters

B+ Tree

 B Tree

Structure

Separate leaf nodes for data storage and internal nodes for indexing

Nodes store both keys and data values

Leaf Nodes

Leaf nodes form a linked list for efficient range-based queries

Leaf nodes do not form a linked list

Order

Higher order (more keys)

 Lower order (fewer keys)

Key Duplication

Typically allows key duplication in leaf nodes

Usually does not allow key duplication

Disk Access

Better disk access due to sequential reads in a linked list structure

More disk I/O due to non-sequential reads in internal nodes

Applications

Database systems, file systems, where range queries are common

In-memory data structures, databases, general-purpose use

Performance

Better performance for range queries and bulk data retrieval

Balanced performance for search, insert, and delete operations

Memory Usage

Requires more memory for internal nodes

Requires less memory as keys and values are stored in the same node

Implementation of B+ Tree

In order, to implement dynamic multilevel indexing, B-tree and B+ tree are generally employed. The drawback of the B-tree used for indexing, however, is that it stores the data pointer (a pointer to the disk file block containing the key value), corresponding to a particular key value, along with that key value in the node of a B-tree. This technique greatly reduces the number of entries that can be packed into a node of a B-tree, thereby contributing to the increase in the number of levels in the B-tree, hence increasing the search time of a record. B+ tree eliminates the above drawback by storing data pointers only at the leaf nodes of the tree. Thus, the structure of the leaf nodes of a B+ tree is quite different from the structure of the internal nodes of the B tree. It may be noted here that, since data pointers are present only at the leaf nodes, the leaf nodes must necessarily store all the key values along with their corresponding data pointers to the disk file block, in order to access them. 

Moreover, the leaf nodes are linked to providing ordered access to the records. The leaf nodes, therefore form the first level of the index, with the internal nodes forming the other levels of a multilevel index. Some of the key values of the leaf nodes also appear in the internal nodes, to simply act as a medium to control the searching of a record. From the above discussion, it is apparent that a B+ tree, unlike a B-tree, has two orders, ‘a’ and ‘b’, one for the internal nodes and the other for the external (or leaf) nodes. 

Structure of B+ Trees

1

B+ Trees contain two types of nodes:

  • Internal Nodes: Internal Nodes are the nodes that are present in at least n/2 record pointers, but not in the root node,
  • Leaf Nodes: Leaf Nodes are the nodes that have n pointers.

The Structure of the Internal Nodes of a B+ Tree of Order ‘a’ is as Follows

  • Each internal node is of the form: <P1, K1, P2, K2, ….., Pc-1, Kc-1, Pc> where c <= a and each Pi is a tree pointer (i.e points to another node of the tree) and, each Ki is a key-value (see diagram-I for reference).
  • Every internal node has : K1 < K2 < …. < Kc-1
  • For each search field value ‘X’ in the sub-tree pointed at by Pi, the following condition holds: Ki-1 < X <= Ki, for 1 < I < c and, Ki-1 < X, for i = c (See diagram I for reference)
  • Each internal node has at most ‘aa tree pointers.
  • The root node has, at least two tree pointers, while the other internal nodes have at least \ceil(a/2) tree pointers each.
  • If an internal node has ‘c’ pointers, c <= a, then it has ‘c – 1’ key values.
Structure of  Internal Node

Structure of  Internal Node

 The Structure of the Leaf Nodes of a B+ Tree of Order ‘b’ is as Follows

  • Each leaf node is of the form: <<K1, D1>, <K2, D2>, ….., <Kc-1, Dc-1>, Pnext> where c <= b and each Di is a data pointer (i.e points to actual record in the disk whose key value is Ki or to a disk file block containing that record) and, each Ki is a key value and, Pnext points to next leaf node in the B+ tree (see diagram II for reference).
  • Every leaf node has : K1 < K2 < …. < Kc-1, c <= b
  • Each leaf node has at least \ceil(b/2) values.
  • All leaf nodes are at the same level.
Structure of Lead Node

Structure of Lead Node

Diagram-II Using the Pnext pointer it is viable to traverse all the leaf nodes, just like a linked list, thereby achieving ordered access to the records stored in the disk. 

Tree Pointer

Tree Pointer

Searching a Record in B+ Trees

1

Searching in B+ Tree

Let us suppose we have to find 58 in the B+ Tree. We will start by fetching from the root node then we will move to the leaf node, which might contain a record of 58. In the image given above, we will get 58 between 50 and 70. Therefore, we will we are getting a leaf node in the third leaf node and get 58 there. If we are unable to find that node, we will return that ‘record not founded’ message.

Insertion in B+ Trees

Insertion in B+ Trees is done via the following steps.

  • Every element in the tree has to be inserted into a leaf node. Therefore, it is necessary to go to a proper leaf node.
  • Insert the key into the leaf node in increasing order if there is no overflow.

For more, refer to Insertion in a B+ Trees.

Deletion in B+Trees

Deletion in B+ Trees is just not deletion but it is a combined process of Searching, Deletion, and Balancing. In the last step of the Deletion Process, it is mandatory to balance the B+ Trees, otherwise, it fails in the property of B+ Trees.

For more, refer to Deletion in B+ Trees.

Advantages of B+Trees

  • A B+ tree with ‘l’ levels can store more entries in its internal nodes compared to a B-tree having the same ‘l’ levels. This accentuates the significant improvement made to the search time for any given key. Having lesser levels and the presence of Pnext pointers imply that the B+ trees is very quick and efficient in accessing records from disks. 
  • Data stored in a B+ tree can be accessed both sequentially and directly.
  • It takes an equal number of disk accesses to fetch records.
  • B+trees have redundant search keys, and storing search keys repeatedly is not possible. 

Disadvantages of B+ Trees

  • The major drawback of B-tree is the difficulty of traversing the keys sequentially. The B+ tree retains the rapid random access property of the B-tree while also allowing rapid sequential access.

Application of B+ Trees

  • Multilevel Indexing
  • Faster operations on the tree (insertion, deletion, search)
  • Database indexing

Conclusion

In conclusion, B+ trees are an essential component of contemporary database systems since they significantly improve database performance and make efficient data management possible.

FAQs on B+ Trees

Q.1: What is a B+ Tree?

Answer:

B+ Tree is balanced binary search tree that can simply be a B Tree, where data is stored in keys, not key-value pairs.

Q.2: What is the advantage of the B+ Tree?

Answer:

The height of the B+ Trees is mostly balanced and is comparatively lesser than B-Trees.

Q.3: Where are B+ Trees used?

Answer:

B+ Trees are often used for disk-based storage systems.



Previous Article
Next Article

Similar Reads

Complexity of different operations in Binary tree, Binary Search Tree and AVL tree
In this article, we will discuss the complexity of different operations in binary trees including BST and AVL trees. Before understanding this article, you should have a basic idea about Binary Tree, Binary Search Tree, and AVL Tree. The main operations in a binary tree are: search, insert and delete. We will see the worst-case time complexity of t
4 min read
Introduction to R-tree
R-tree is a tree data structure used for storing spatial data indexes in an efficient manner. R-trees are highly useful for spatial data queries and storage. Some of the real-life applications are mentioned below: Indexing multi-dimensional information.Handling geospatial coordinates.Implementation of virtual maps.Handling game data. Example: R-Tre
1 min read
Introduction of B-Tree
The limitations of traditional binary search trees can be frustrating. Meet the B-Tree, the multi-talented data structure that can handle massive amounts of data with ease. When it comes to storing and searching large amounts of data, traditional binary search trees can become impractical due to their poor performance and high memory usage. B-Trees
15+ min read
Difference between B tree and B+ tree
B-Tree: B-Tree is known as a self-balancing tree as its nodes are sorted in the inorder traversal. In B-tree, a node can have more than two children. B-tree has a height of logM N (Where ‘M’ is the order of tree and N is the number of nodes). And the height is adjusted automatically at each update. In the B-tree data is sorted in a specific order,
3 min read
Difference between Binary tree and B-tree
B-Tree : B-Tree is known as a self-balancing tree as its nodes are sorted in the inorder traversal. Unlike the binary trees, in B-tree, a node can have more than two children. B-tree has a height of logM N (Where ‘M’ is the order of tree and N is the number of nodes). And the height is adjusts automatically at each update. In the B-tree data is sor
7 min read
Introduction of Relational Algebra in DBMS
Pre-Requisite: Relational Model in DBMS Relational Algebra is a procedural query language. Relational algebra mainly provides a theoretical foundation for relational databases and SQL. The main purpose of using Relational Algebra is to define operators that transform one or more input relations into an output relation. Given that these operators ac
4 min read
Introduction of Relational Model and Codd Rules in DBMS
Pre-Requisite: Relational Model in DBMS It was proposed by Dr. E.F. Codd. It uses the concept of relations to represent each and every file. Relations are Two-Dimensional Tables. It is easy to implement and easy to simplification in the operations to manipulate the data. This is the most popular data model. It is simple to implement. It uses the pr
12 min read
Introduction of Theory of Computation
Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata. Automata* enables scientists to understand how machines compute the functions and solve problems. The main motivation behind dev
3 min read
PL/SQL Introduction
PL/SQL is a block structured language that enables developers to combine the power of SQL with procedural statements.All the statements of a block are passed to oracle engine all at once which increases processing speed and decreases the traffic. Basics of PL/SQL•PL/SQL stands for Procedural Language extensions to the Structured Query Language (SQL
6 min read
Discrete Maths | Generating Functions-Introduction and Prerequisites
Prerequisite - Combinatorics Basics, Generalized PnC Set 1, Set 2 Definition : Generating functions are used to represent sequences efficiently by coding the terms of a sequence as coefficients of powers of a variable (say) [Tex]\big x [/Tex]in a formal power series. Now with the formal definition done, we can take a minute to discuss why should we
5 min read
Article Tags :