Difference Between B Tree and B plus Tree

Introduction  

This blog is about a type of Data Structure called the B tree and its variation, known as the B+ tree. We will understand them in detail, their features and examples, and how they are used effectively in  DBMS(Database management systems) to create and manage indexes.

Let's start with the B tree.

B Tree

B tree is a popular terminology in computer science. B tree is a self-balancing binary search tree ( A binary search tree is said to be self-balancing when it automatically keeps its height small in the face of arbitrary item insertions and deletions, where height is the maximum number of levels below the root ) that helps in maintaining and sorting data. It also provides operations like search, deletion, insertion, and sequential access. The data and the keys can be stored in both the internal and leaf nodes in a B-tree.

B tree is also known as an m-way tree, where m is used to determine the order of the tree. A  B-tree can have more than one key and more than two children based on the value of m.

A B-tree is a generalized BST(Binary Search Tree) in which any node can have more than two children. Each internal node in a B-tree contains several keys. These keys separate the values further from the sub-trees. The internal nodes can have variable numbers of child nodes arranged within a predefined range.

When any data is removed or inserted from any respective node, there is a change in the number of child nodes. Internal nodes may be split or joined to maintain the predefined range according to the situation. A range of child nodes is permitted in B Tree, due to which the predefined range has to be maintained.

Note: B Tree and Binary tree are two different things, don't get confused with the name.

Example to understand the B tree :

Source: wikimedia.com

The above is an order-5 B-tree or 5-way B-Tree (meaning, m is 5) where the leaves nodes have enough space to store up to 3 data records. It is self-balanced, and since the tree's height is uniformly the same and every node is at least half full, we are guaranteed that the asymptotic performance( or the evaluation of the performance of an algorithm in terms of the input size n) is O(log n), where n denotes the size of the collection here. 

Read about Recursive Relationship in DBMS

B+ Tree

A B+ tree is the same as a B tree; the only difference is that in the B+ tree, there is an additional level added at the bottom with linked leaves. Also, unlike the B tree, each node in a B+ tree contains only keys and not key-value pairs.

A B+ tree is an n-array tree with a node consisting of many children per node. The root may be a leaf or a node that contains more than two children. A B+ tree consists of a root, internal nodes, and leaves.

The primary value of the B+ tree is in storing and maintaining the data so that the data is not lost.

Example of B+ Tree

Source: cburch.com

In this example:

• The tree's root node is 30(there will be only one root node
• The intermediary layer of nodes acts as a pointer to leaf nodes. These nodes do not store the actual records.
• The nodes to the left of the root contain the initial value of the root, i.e., 20 and 40, respectively.
• There is only one leaf node in the B+ tree, having values: 10, 15, 22, 25, 27, 32, 35.
• Since all the leaf nodes are already balanced, searching any record will be easier.

Read About - Specialization and Generalization in DBMS

Role of B trees and B+ tree in DBMS(Database Management Systems)

Since data needs to be stored and managed for computations. And main memory is the primary storage; we cannot store everything because it is volatile and expensive. The concept of secondary storage comes to underplay as secondary storage is non-volatile and less expensive.

File organization defines how the file records are mapped onto disk blocks, or we can say that the File organization is a logical relationship between various records. There are different types of file organization. One of which is B+ tree file organization. It uses the concept of a B+ tree to store the records.

Advantages of B trees and B+ trees

The following are the advantages of B trees:

• B-trees provide logarithmic O(log(n)) time complexity in the insert, delete, and search operations.
• Thus searching is quite faster in B trees.

The following are the advantages of using B+ trees are

• We can fetch records in an equal number of disk accesses.
• Searching the queries became faster as the data is stored in leaf nodes only.
• In B+ trees, keys are used for indexing.
• Records stored in a B+ tree can be accessed sequentially and directly.
  
  You can also read about the Multiple Granularity Locking

FAQs

1. What is a file?
   A File is a collection of records(or data) stored in binary format.
    
2. What are the advantages of B Tree?
   The following are the advantages of B trees:
   B-trees provide logarithmic O(log(n)) time complexity in the insert, delete, and search operations.
   Thus searching is quite faster in B trees.
    
3. What are the advantages of the B+ Tree?
   The following are the advantages of B+ trees:
   We can fetch records in an equal number of disk accesses.
   Searching the queries became faster as the data is stored in leaf nodes only
   In B+ trees, keys are used for indexing.
   Records stored in a B+ tree can be accessed sequentially and directly.