数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


B+ Trees



The B+ trees are extensions of B trees designed to make the insertion, deletion and searching operations more efficient.

The properties of B+ trees are similar to the properties of B trees, except that the B trees can store keys and records in all internal nodes and leaf nodes while B+ trees store records in leaf nodes and keys in internal nodes. One profound property of the B+ tree is that all the leaf nodes are connected to each other in a single linked list format and a data pointer is available to point to the data present in disk file. This helps fetch the records in equal numbers of disk access.

Since the size of main memory is limited, B+ trees act as the data storage for the records that couldn’t be stored in the main memory. For this, the internal nodes are stored in the main memory and the leaf nodes are stored in the secondary memory storage.

b plus tree

Properties of B+ trees

  • Every node in a B+ Tree, except root, will hold a maximum of m children and (m-1) keys, and a minimum of $\mathrm{\left \lceil \frac{m}{2} ight ceil}$ children and $\mathrm{\left \lceil \frac{m-1}{2} ight ceil}$ keys, since the order of the tree is m.

  • The root node must have no less than two children and at least one search key.

  • All the paths in a B tree must end at the same level, i.e. the leaf nodes must be at the same level.

  • A B+ tree always maintains sorted data.

Basic Operations of B+ Trees

The operations supported in B+ trees are Insertion, deletion and searching with the time complexity of O(log n) for every operation.

They are almost similar to the B tree operations as the base idea to store data in both data structures is same. However, the difference occurs as the data is stored only in the leaf nodes of a B+ trees, unlike B trees.

Insertion operation

The insertion to a B+ tree starts at a leaf node.

Step 1 − Calculate the maximum and minimum number of keys to be added onto the B+ tree node.

calculate number of keys

Step 2 − Insert the elements one by one accordingly into a leaf node until it exceeds the maximum key number.

Insert elements

Step 3 − The node is split into half where the left child consists of minimum number of keys and the remaining keys are stored in the right child.

node split

Step 4 − But if the internal node also exceeds the maximum key property, the node is split in half where the left child consists of the minimum keys and remaining keys are stored in the right child. However, the smallest number in the right child is made the parent.

insert into b plus tree

Step 5 − If both the leaf node and internal node have the maximum keys, both of them are split in the similar manner and the smallest key in the right child is added to the parent node.

b_plus_tree_order_4

Example

Following are the implementations of this operation in various programming languages −

// C program for Bplus tree
#include <stdio.h>
#include <stdlib.h>
struct BplusTree {
   int *d;
   struct BplusTree **child_ptr;
   int l;
   int n;
};
struct BplusTree *r = NULL, *np = NULL, *x = NULL;
struct BplusTree* init() {
    //to create nodes
   int i;
   np = (struct BplusTree*)malloc(sizeof(struct BplusTree));
   np->d = (int*)malloc(6 * sizeof(int)); // order 6
   np->child_ptr = (struct BplusTree**)malloc(7 * sizeof(struct BplusTree*));
   np->l = 1;
   np->n = 0;
   for (i = 0; i < 7; i++) {
      np->child_ptr[i] = NULL;
   }
   return np;
}
void traverse(struct BplusTree *p) {
    //traverse tree
   printf("
");
   int i;
   for (i = 0; i < p->n; i++) {
      if (p->l == 0) {
         traverse(p->child_ptr[i]);
      }
      printf(" %d", p->d[i]);
   }
   if (p->l == 0) {
      traverse(p->child_ptr[i]);
   }
   printf("
");
}

void sort(int *p, int n) {
   int i, j, t;
   for (i = 0; i < n; i++) {
      for (j = i; j <= n; j++) {
         if (p[i] > p[j]) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
         }
      }
   }
}

int split_child(struct BplusTree *x, int i) {
   int j, mid;
   struct BplusTree *np1, *np3, *y;
   np3 = init();
   np3->l = 1;
   if (i == -1) {
      mid = x->d[2];
      x->d[2] = 0;
      x->n--;
      np1 = init();
      np1->l = 0;
      x->l = 1;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = x->d[j];
         np3->child_ptr[j - 3] = x->child_ptr[j];
         np3->n++;
         x->d[j] = 0;
         x->n--;
      }
      for (j = 0; j < 6; j++) {
         x->child_ptr[j] = NULL;
      }
      np1->d[0] = mid;
      np1->child_ptr[np1->n] = x;
      np1->child_ptr[np1->n + 1] = np3;
      np1->n++;
      r = np1;
   } else {
      y = x->child_ptr[i];
      mid = y->d[2];
      y->d[2] = 0;
      y->n--;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = y->d[j];
         np3->n++;
         y->d[j] = 0;
         y->n--;
      }
      x->child_ptr[i + 1] = y;
      x->child_ptr[i + 1] = np3;
   }
   return mid;
}

void insert(int a) {
   int i, t;
   x = r;
   if (x == NULL) {
      r = init();
      x = r;
   } else {
      if (x->l == 1 && x->n == 6) {
         t = split_child(x, -1);
         x = r;
         for (i = 0; i < x->n; i++) {
            if (a > x->d[i] && a < x->d[i + 1]) {
               i++;
               break;
            } else if (a < x->d[0]) {
               break;
            } else {
               continue;
            }
         }
         x = x->child_ptr[i];
      } else {
         while (x->l == 0) {
            for (i = 0; i < x->n; i++) {
               if (a > x->d[i] && a < x->d[i + 1]) {
                  i++;
                  break;
               } else if (a < x->d[0]) {
                  break;
               } else {
                  continue;
               }
            }
            if (x->child_ptr[i]->n == 6) {
               t = split_child(x, i);
               x->d[x->n] = t;
               x->n++;
               continue;
            } else {
               x = x->child_ptr[i];
            }
         }
      }
   }
   x->d[x->n] = a;
   sort(x->d, x->n);
   x->n++;
}

int main() {
   int i, n, t;
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   insert(50);
   printf("Insertion Done");
   printf("
B+ tree:");
   traverse(r);
   return 0;
}

Output

Insertion Done
B+ tree:
 10 20 30 40 50
#include<iostream>
using namespace std;
struct BplusTree {
   int *d;
   BplusTree **child_ptr;
   bool l;
   int n;
}
*r = NULL, *np = NULL, *x = NULL;
BplusTree* init() { //to create nodes 
   int i;
   np = new BplusTree;
   np->d = new int[6];//order 6
   np->child_ptr = new BplusTree *[7];
   np->l = true;
   np->n = 0;
   for (i = 0; i < 7; i++) {
      np->child_ptr[i] = NULL;
   }
   return np;
}

void traverse(BplusTree *p) { //traverse tree 
   cout<<endl;
   int i;
   for (i = 0; i < p->n; i++) {
      if (p->l == false) {
         traverse(p->child_ptr[i]);
      }
      cout << " " << p->d[i];
   }
   if (p->l == false) {
      traverse(p->child_ptr[i]);
   }
   cout<<endl;
}

void sort(int *p, int n) { //sort the tree 
   int i, j, t;
   for (i = 0; i < n; i++) {
      for (j = i; j <= n; j++) {
         if (p[i] >p[j]) {
            t = p[i];
            p[i] = p[j];
            p[j] = t;
         }
      }
   }
}

int split_child(BplusTree *x, int i) {
   int j, mid;
   BplusTree *np1, *np3, *y;
   np3 = init();
   np3->l = true;
   if (i == -1) {
      mid = x->d[2];
      x->d[2] = 0;
      x->n--;
      np1 = init();
      np1->l = false;
      x->l = true;
      for (j = 3; j < 6; j++) {
         np3->d[j - 3] = x->d[j];
         np3->child_ptr[j - 3] = x->child_ptr[j];
         np3->n++;
         x->d[j] = 0;
         x->n--;
      }
      for (j = 0; j < 6; j++) {
         x->child_ptr[j] = NULL;
      }
      np1->d[0] = mid;
      np1->child_ptr[np1->n] = x;
      np1->child_ptr[np1->n + 1] = np3;
      np1->n++;
      r = np1;
   } else {
      y = x->child_ptr[i];
      mid = y->d[2];
      y->d[2] = 0;
      y->n--;
      for (j = 3; j <6 ; j++) {
         np3->d[j - 3] = y->d[j];
         np3->n++;
         y->d[j] = 0;
         y->n--;
      }
      x->child_ptr[i + 1] = y;
      x->child_ptr[i + 1] = np3;
   }
   return mid;
}

void insert(int a) {
   int i, t;
   x = r;
   if (x == NULL) {
      r = init();
      x = r;
   } else {
      if (x->l== true && x->n == 6) {
         t = split_child(x, -1);
         x = r;
         for (i = 0; i < (x->n); i++) {
            if ((a >x->d[i]) && (a < x->d[i + 1])) {
            i++;
            break;
         } else if (a < x->d[0]) {
            break;
         } else {
            continue;
         }
      }
      x = x->child_ptr[i];
   } else {
      while (x->l == false) {
         for (i = 0; i < (x->n); i++) {
            if ((a >x->d[i]) && (a < x->d[i + 1])) {
               i++;
               break;
            } else if (a < x->d[0]) {
               break;
            } else {
               continue;
            }
         }
         if ((x->child_ptr[i])->n == 6) {
            t = split_child(x, i);
            x->d[x->n] = t;
            x->n++;
            continue;
         } else {
            x = x->child_ptr[i];
         }
      }
   }
}
   x->d[x->n] = a;
   sort(x->d, x->n);
   x->n++;
}

int main() {
   int i, n, t;
   insert(10);
   insert(20);
   insert(30);
   insert(40);
   insert(50);
   cout<<"Insertion Done";
   cout<<"
B+ tree:";
   traverse(r);
}

Output

Insertion Done
B+ tree:
 10 20 30 40 50
//Java program for Bplus code
import java.util.*;
class BplusTree {
   int[] d;
   BplusTree[] child_ptr;
   boolean l;
   int n;
}
public class Main {
   static BplusTree r = null, np = null, x = null;
   static BplusTree init() { // to create nodes 
      int i;
      np = new BplusTree();
      np.d = new int[6]; // order 6
      np.child_ptr = new BplusTree[7];
      np.l = true;
      np.n = 0;
      for (i = 0; i < 7; i++) {
         np.child_ptr[i] = null;
      }
      return np;
   }
   static void traverse(BplusTree p) { // traverse tree 
      int i;
      for (i = 0; i < p.n; i++) {
         if (p.l == false) {
            traverse(p.child_ptr[i]);
         }
         System.out.print(" " + p.d[i]);
      }
      if (p.l == false) {
         traverse(p.child_ptr[i]);
      }
      System.out.println();
   }
   static void sort(int[] p, int n) { // sort the tree 
      int i, j, t;
      for (i = 0; i < n; i++) {
         for (j = i; j <= n; j++) {
            if (p[i] > p[j]) {
               t = p[i];
               p[i] = p[j];
               p[j] = t;
            }
         }
      }
   }
   static int split_child(BplusTree x, int i) {
      int j, mid;
      BplusTree np1, np3, y;
      np3 = init();
      np3.l = true;
      if (i == -1) {
         mid = x.d[2];
         x.d[2] = 0;
         x.n--;
         np1 = init();
         np1.l = false;
         x.l = true;
         for (j = 3; j < 6; j++) {
            np3.d[j - 3] = x.d[j];
            np3.child_ptr[j - 3] = x.child_ptr[j];
            np3.n++;
            x.d[j] = 0;
            x.n--;
         }
         for (j = 0; j < 6; j++) {
            x.child_ptr[j] = null;
         }
         np1.d[0] = mid;
         np1.child_ptr[np1.n] = x;
         np1.child_ptr[np1.n + 1] = np3;
         np1.n++;
         r = np1;
      } else {
         y = x.child_ptr[i];
         mid = y.d[2];
         y.d[2] = 0;
         y.n--;
         for (j = 3; j < 6; j++) {
            np3.d[j - 3] = y.d[j];
            np3.n++;
            y.d[j] = 0;
            y.n--;
         }
         x.child_ptr[i + 1] = y;
         x.child_ptr[i + 1] = np3;
      }
      return mid;
   }
   static void insert(int a) {
      int i, t;
      x = r;
      if (x == null) {
         r = init();
         x = r;
      } else {
         if (x.l == true && x.n == 6) {
            t = split_child(x, -1);
            x = r;
            for (i = 0; i < x.n; i++) {
               if (a > x.d[i] && a < x.d[i + 1]) {
                  i++;
                  break;
               } else if (a < x.d[0]) {
                  break;
               } else {
                  continue;
               }
            }
            x = x.child_ptr[i];
         } else {
            while (x.l == false) {
               for (i = 0; i < x.n; i++) {
                  if (a > x.d[i] && a < x.d[i + 1]) {
                     i++;
                     break;
                  } else if (a < x.d[0]) {
                     break;
                  } else {
                     continue;
                  }
               }
               if (x.child_ptr[i].n == 6) {
                  t = split_child(x, i);
                  x.d[x.n] = t;
                  x.n++;
                  continue;
               } else {
                  x = x.child_ptr[i];
               }
            }
         }
      }
      x.d[x.n] = a;
      sort(x.d, x.n);
      x.n++;
   }
   public static void main(String[] args) {
      int i, n, t;
      insert(10);
      insert(20);
      insert(30);
      insert(40);
      insert(50);
	  System.out.print("Insertion Done");
      System.out.println("
B+ tree:");
      traverse(r);
   }
}

Output

Insertion Done
B+ tree:
 10 20 30 40 50
#Python Program for Bplus tree
#to create nodes
class BplusTree:
    def __init__(self):
        self.d = [0] * 6  # order 6
        self.child_ptr = [None] * 7
        self.l = True  
        self.n = 0
def init():
    np = BplusTree()
    np.l = True
    np.n = 0
    return np
#traverse tree
def traverse(p):
    for i in range(p.n):
        if not p.l:
            traverse(p.child_ptr[i])
        print(" ", p.d[i], end="")
    if not p.l:
        traverse(p.child_ptr[p.n])
    print()
#sort the tree
def sort(p, n):
    for i in range(n):
        for j in range(i, n + 1):
            if p[i] > p[j]:
                p[i], p[j] = p[j], p[i]
def split_child(x, i):
    np3 = init()
    np3.l = True
    if i == -1:
        mid = x.d[2]
        x.d[2] = 0
        x.n -= 1
        np1 = init()
        np1.l = False
        x.l = True
        for j in range(3, 6):
            np3.d[j - 3] = x.d[j]
            np3.child_ptr[j - 3] = x.child_ptr[j]
            np3.n += 1
            x.d[j] = 0
            x.n -= 1
        for j in range(6):
            x.child_ptr[j] = None
        np1.d[0] = mid
        np1.child_ptr[np1.n] = x
        np1.child_ptr[np1.n + 1] = np3
        np1.n += 1
        r = np1
    else:
        y = x.child_ptr[i]
        mid = y.d[2]
        y.d[2] = 0
        y.n -= 1
        for j in range(3, 6):
            np3.d[j - 3] = y.d[j]
            np3.n += 1
            y.d[j] = 0
            y.n -= 1
        x.child_ptr[i + 1] = y
        x.child_ptr[i + 1] = np3
    return mid
def insert(a):
    global r, x
    x = r
    if x is None:
        r = init()
        x = r
    else:
        if x.l and x.n == 6:
            t = split_child(x, -1)
            x = r
            for i in range(x.n):
                if a > x.d[i] and a < x.d[i + 1]:
                    i += 1
                    break
                elif a < x.d[0]:
                    break
                else:
                    continue
            x = x.child_ptr[i]
        else:
            while not x.l:
                for i in range(x.n):
                    if a > x.d[i] and a < x.d[i + 1]:
                        i += 1
                        break
                    elif a < x.d[0]:
                        break
                    else:
                        continue
                if x.child_ptr[i].n == 6:
                    t = split_child(x, i)
                    x.d[x.n] = t
                    x.n += 1
                    continue
                else:
                    x = x.child_ptr[i]
    x.d[x.n] = a
    sort(x.d, x.n)
    x.n += 1
r = None
x = None
insert(10)
insert(20)
insert(30)
insert(40)
insert(50)
print("Insertion Done")
print("B+ tree:")
traverse(r)

Output

Insertion Done
B+ tree:
  10  20  30  40  50