B+ 树

2025年4月1日 | 3 分钟阅读

插入

步骤 1 找到正确的叶子节点 L
步骤 2 尝试将（键，指针）对放入 L
步骤 2a 如果 L 有足够的空间，则放入。否则，拆分 L（分为 L 和一个新节点 L2）
步骤 2b 将 L 的条目均匀地重新分配给 L 和 L2
步骤 2c 向上复制中间键，即递归地将中间键插入 L 的父节点，并将 L2 的指针添加到 L 的父节点
步骤 3 插入内部节点 V 时
步骤 3a 如果 V 有足够的空间，则放入。否则，拆分 V（分为 V 和一个新节点 V2）
步骤 3b 将 V 的条目均匀地重新分配给 V 和 V2
步骤 3c 向上移动中间键。（与叶子节点拆分进行对比。）
步骤 4 拆分使树“增长”，使其更宽。如果根节点拆分，则树的高度增加一。

程序

#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
struct BplusTreeNode
{
    int *data;
    BplusTreeNode **child_ptr;
    bool leaf;
    int n;
}*root = NULL, *np = NULL, *x = NULL;
BplusTreeNode * init()
{
    int i;
    np = new BplusTreeNode;
    np->data = new int[5];
    np->child_ptr = new BplusTreeNode *[6];
    np->leaf = true;
    np->n = 0;
    for (i = 0; i < 6; i++)
    {
        np->child_ptr[i] = NULL;
    }
    return np;
}
void traverse(BplusTreeNode *p)
{
    cout<<endl;
    int i;
    for (i = 0; i < p->n; i++)
    {
        if (p->leaf == false)
        {
            traverse(p->child_ptr[i]);
        }
        cout << " " << p->data[i];
    } 
    if (p->leaf == false)
    {
        traverse(p->child_ptr[i]);
    }
    cout<<endl;
}
void sort(int *p, int n)
{
    int i, j, temp;
    for (i = 0; i < n; i++)
    {
        for (j = i; j <= n; j++)
        {
            if (p[i] > p[j])
            {
                temp = p[i];
                p[i] = p[j];
                p[j] = temp;
            }
        }
    }
}
int split_child(BplusTreeNode *x, int i)
{
    int j, mid;
    BplusTreeNode *np1, *np3, *y;
    np3 = init();
    np3->leaf = true;
    if (i == -1)
    {
        mid = x->data[2];
        x->data[2] = 0;
        x->n--;
        np1 = init();
        np1->leaf = false;
        x->leaf = true;
        for (j = 3; j < 5; j++)
        {
            np3->data[j - 3] = x->data[j];
            np3->child_ptr[j - 3] = x->child_ptr[j];
            np3->n++;
            x->data[j] = 0;
            x->n--;
        }
        for(j = 0; j < 6; j++)
        {
            x->child_ptr[j] = NULL;
        }
        np1->data[0] = mid;
        np1->child_ptr[np1->n] = x;
        np1->child_ptr[np1->n + 1] = np3;
        np1->n++;
        root = np1;
    }
    else
    {
        y = x->child_ptr[i];
        mid = y->data[2];
        y->data[2] = 0;
        y->n--;
        for (j = 3; j < 5; j++)
        {
            np3->data[j - 3] = y->data[j];
            np3->n++;
            y->data[j] = 0;
            y->n--;
        }
        x->child_ptr[i + 1] = y;
        x->child_ptr[i + 1] = np3; 
    }
    return mid;
}
void insert(int a)
{
    int i, temp;
    x = root;
    if (x == NULL)
    {
        root = init();
        x = root;
    }
    else
    {
        if (x->leaf == true && x->n == 5)
        {
            temp = split_child(x, -1);
            x = root;
            for (i = 0; i < (x->n); i++)
            {
                if ((a > x->data[i]) && (a < x->data[i + 1]))
                {
                    i++;
                    break;
                }
                else if (a < x->data[0])
                {
                    break;
                }
                else
                {
                    continue;
                }
            }
            x = x->child_ptr[i];
        }
        else
        {
            while (x->leaf == false)
            {
            for (i = 0; i < (x->n); i++)
            {
                if ((a > x->data[i]) && (a < x->data[i + 1]))
                {
                    i++;
                    break;
                }
                else if (a < x->data[0])
                {
                    break;
                }
                else
                {
                    continue;
                }
            }
                if ((x->child_ptr[i])->n == 5)
                {
                    temp = split_child(x, i);
                    x->data[x->n] = temp;
                    x->n++;
                    continue;
                }
                else
                {
                    x = x->child_ptr[i];
                }
            }
        }
    }
    x->data[x->n] = a;
    sort(x->data, x->n);
    x->n++;
}
int main()
{
    int i, n, t;
    cout<<"enter the no of elements to be inserted\n";
    cin>>n;
    for(i = 0; i < n; i++)
    {
        cout<<"enter the element\n";
        cin>>t;
        insert(t);
    }
    cout<<"traversal of constructed tree\n";
    traverse(root);
    return 0;
}

输出

enter the no of elements to be inserted                                                                                          
5                                                                                                                                
enter the element                                                                                                                
10                                                                                                                               
enter the element                                                                                                                
30                                                                                                                               
enter the element                                                                                                                
20                                                                                                                               
enter the element                                                                                                                
40                                                                                                                               
enter the element                                                                                                                
60                                                                                                                               
traversal of constructed tree                                                                                                    
                                                                                                                                 
 10 20 30 40 60                                                                                                                  
                 

下一主题#

B+ 树

插入

程序

输出

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

B+ 树

插入

程序

输出

相关帖子

以最小成本连接 n 根绳子

查找标记索引的最大数量问题

握手引理和有趣的树属性 - DSA

DS 中的二叉树遍历

构建堆时，堆的结构是唯一的吗

使用 RMQ 在二叉树中查找 LCA

B 树插入

查找给定矩阵中每个索引的最大路径长度

使用栈实现队列

与给定数字最接近的三元组和

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器