EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial B+ Tree in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search

Related Courses

All in One Data Science Course

Oracle DBA Course

SQL Certification Course

B+ Tree in Data Structure

By Priya PedamkarPriya Pedamkar

B+ Tree in Data Structure

Introduction to B+ Tree in Data Structure

B+ Tree in Data Structure is an N-array tree in which a node has multiple children. Its components are root, internal nodes, and leaves. It allows very efficient insertion and deletion operation. Though a complex concept, It is a highly effective data structure for optimizing processing performance. It is quite useful in situations that involve large datasets where processing speed is very important.

Visual Representation of B+ Tree in Data Structure

Below is the visual representation:

Visual Representation of B+ Tree

Implementation of B+ Tree

Below is the code:

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

Code:

#include<stdio.h>
#include<conio.h>
#define Macro 4
struct node
{
int n;
int keys[Macro - 1];
struct node *p[Macro];
}*root=NULL;
enum KeyStatus { dupl,SearchFailure,Success,insrit,LessKeys };
void insert(int x);
void display(struct node *root,int);
void delete(int x);
enum KeyStatus ins(struct node *r, int x, int* y, struct node** u);
int searchPos(int x,int *key_arr, int n);
enum KeyStatus del(struct node *r, int x);
void main()
{
int k;
int op;
for(;;)
{
printf("\n1.Insert");
printf("\n2.Delete");
printf("\n3.Display");
printf("\n4.Quit");
printf("\nEnter the option : ");
scanf("%d",&op);
switch(op)
{
case 1:
printf("\nEnter the element : ");
scanf("%d",&k);
insert(k);
break;
case 2:
printf("\nEnter the element : ");
scanf("%d",&k);
delete(k);
break;
case 3:
printf("\nB+ tree is :\n");
display(root,0);
break;
case 4:
exit(1);
default:
printf("\nInvalid Option.");
break;
}
}
}
void insert(int k)
{
struct node *newnode;
int upK;
enum KeyStatus val;
val = ins(root, k, &upK, &newnode);
if (val == dupl)
printf("\nElement already present.");
if (val == insrit)
{
struct node *uproot = root;
root=malloc(sizeof(struct node));
root -> n = 1;
root -> keys[0] = upK;
root -> p[0] = uproot;
root->p[1] = newnode;
}
}
enum KeyStatus ins(struct node *ptr, int k, int *upK,struct node **newnode)
{
struct node *nptr, *lptr;
int pos, i, n,splitPos;
int nK, lK;
enum KeyStatus val;
if (ptr == NULL)
{
*newnode = NULL;
*upK = k;
return insrit;
}
n = ptr -> n;
pos = searchPos(k, ptr->keys, n);
if (pos < n && k == ptr -> keys[pos])
return dupl;
val = ins(ptr->p[pos], k, &nK, &nptr);
if (val != insrit)
return val;
if (n < Macro - 1)
{
pos = searchPos(nK, ptr->keys, n);
for (i=n; i>pos; i--)
{
ptr -> keys[i] = ptr -> keys[i-1];
ptr -> p[i+1] = ptr -> p[i];
}
ptr -> keys[pos] = nK;
ptr -> p[pos+1] = nptr;
++ptr -> n;
return Success;
}
if (pos == Macro - 1)
{
lK = nK;
lptr = nptr;
}
else
{
lK = ptr -> keys[Macro-2];
lptr = ptr -> p[Macro-1];
for (i = Macro - 2; i > pos; i--)
{
ptr->keys[i] = ptr->keys[i-1];
ptr->p[i+1] = ptr->p[i];
}
ptr -> keys[pos] = nK;
ptr -> p[pos+1] = nptr;
}
splitPos = (Macro - 1)/2;
(*upK) = ptr->keys[splitPos];
(*newnode)=malloc(sizeof(struct node));
ptr -> n = splitPos;
(*newnode)->n = Macro - 1 - splitPos;
for (i=0; i < (*newnode)->n; i++)
{
(*newnode)->p[i] = ptr->p[i + splitPos + 1];
if(i < (*newnode)->n - 1)
(*newnode)->keys[i] = ptr->keys[i + splitPos + 1];
else
(*newnode)->keys[i] = lK;
}
(*newnode)->p[(*newnode)->n] = lptr;
return insert;
}
void display(struct node *ptr, int bl)
{
if (ptr)
{
int i;
for(i=1;i<=bl;i++)
printf(" ");
for (i=0; i < ptr->n; i++)
printf("%d ",ptr->keys[i]);
printf("\n");
for (i=0; i <= ptr->n; i++)
display(ptr->p[i], bl + 10);
}
}
int searchPos(int k, int *k_arr, int n)
{
int pos = 0;
while (pos < n && k > k_arr[pos])
pos++;
return pos;
}
void delete(int key)
{
struct node *uproot;
enum KeyStatus value;
value = del(root,key);
switch (value)
{
case SearchFailure:
printf("Key %d is not available\n",key);
break;
case LessKeys:
uproot = root;
root = root->p[0];
free(uproot);
break;
}
}
enum KeyStatus del(struct node *ptr, int k)
{
int pos, i, piv, n ,min;
int *k_arr;
enum KeyStatus val;
struct node **p,*lptr,*rptr;
if (ptr == NULL)
return SearchFailure;
n = ptr -> n;
k_arr = ptr -> keys;
p = ptr->p;
min = (Macro - 1)/2;/*Minimum number of keys*/
pos = searchPos(k, k_arr, n);
if (p[0] == NULL)
{
if (pos == n || k < k_arr[pos])
return SearchFailure;
for (i=pos+1; i < n; i++)
{
k_arr[i-1] = k_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys;
}
if (pos < n && k == k_arr[pos])
{
struct node *qp = p[pos], *qp1;
int nkey;
for(;;)
{
nkey = qp->n;
qp1 = qp->p[nkey];
if (qp1 == NULL)
break;
qp = qp1;
}
k_arr[pos] = qp -> keys[nkey-1];
qp -> keys[nkey - 1] = k;
}
val = del(p[pos], k);
if (val != LessKeys)
return val;
if (pos > 0 && p[pos-1]->n > min)
{
piv = pos - 1; /*pivot for left and right node*/
lptr = p[piv];
rptr = p[pos];
rptr -> p[rptr->n + 1] = rptr->p[rptr->n];
for (i=rptr->n; i>0; i--)
{
rptr->keys[i] = rptr->keys[i-1];
rptr->p[i] = rptr->p[i-1];
}
rptr->n++;
rptr->keys[0] = k_arr[piv];
rptr->p[0] = lptr->p[lptr->n];
k_arr[piv] = lptr->keys[--lptr->n];
return Success;
}
if (pos > min)
{
piv = pos; lptr = p[piv];
rptr = p[piv+1];
lptr->keys[lptr->n] = k_arr[piv];
lptr->p[lptr->n + 1] = rptr->p[0];
k_arr[piv] = rptr->keys[0];
lptr->n++;
rptr->n--;
for (i=0; i < rptr->n; i++)
{
rptr->keys[i] = rptr->keys[i+1];
rptr->p[i] = rptr->p[i+1];
}
rptr->p[rptr->n] = rptr->p[rptr->n + 1];
return Success;
}
if(pos == n)
piv = pos-1;
else
piv = pos;
lptr = p[piv];
rptr = p[piv+1];
lptr->keys[lptr->n] = k_arr[piv];
lptr->p[lptr->n + 1] = rptr->p[0];
for (i=0; i < rptr->n; i++)
{
lptr->keys[lptr->n + 1 + i] = rptr->keys[i];
lptr->p[lptr->n + 2 + i] = rptr->p[i+1];
}
lptr->n = lptr->n + rptr->n +1;
free(rptr);
for (i=pos+1; i < n; i++)
{
k_arr[i-1] = k_arr[i];
p[i] = p[i+1];
}
return --ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys;
}

Output:

Output for Insert Operation:

All in One Data Science Bundle(360+ Courses, 50+ projects)
Python TutorialMachine LearningAWSArtificial Intelligence
TableauR ProgrammingPowerBIDeep Learning
Price
View Courses
360+ Online Courses | 50+ projects | 1500+ Hours | Verifiable Certificates | Lifetime Access
4.7 (86,171 ratings)

We inserted elements one-by-one. Enter the proper option.

1. The first element passed into the tree is 23.

B+ Tree in Data Structure1

2. Similarly, we passed 44, 78, and 90, as shown by the following three screenshots.

Value Passed

B+ Tree in Data Structure3

B+ Tree in Data Structure4

Output for Delete Operation:

Now, let’s delete an element. We chose 44, as shown below.

delete element

Output for Display Operation:

Let’s display the tree now, as shown below.

display tree

Advantages of B+ Tree

  • It offers a very effective mechanism to traverse through the data. It facilitates range as well as partial retrieval.
  • It can be of any size and based on the number of records, its size changes.

Recommended Articles

This is a guide to B+ Tree in Data Structure. Here we discuss an introduction to B+ Tree with Visual representation, implementation, and Advantages. You can also go through our other related articles to learn more –

  1. Linked List in Data Structure
  2. AVL Tree in Data Structure
  3. Types of Trees in Data Structure
  4. What is Decision Tree?
Popular Course in this category
All in One Data Science Bundle (360+ Courses, 50+ projects)
  360+ Online Courses |  1500+ Hours |  Verifiable Certificates |  Lifetime Access
4.7
Price

View Course

Related Courses

Oracle DBA Database Management System Training (2 Courses)4.9
SQL Training Program (7 Courses, 8+ Projects)4.8
0 Shares
Share
Tweet
Share
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2022 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

SPSS, Data visualization with Python, Matplotlib Library, Seaborn Package

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

By signing up, you agree to our Terms of Use and Privacy Policy.

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more