B+ 树插入

2025年3月17日 | 阅读11分钟

B 树和 B+ 树通常用于实现动态多级索引。然而，B 树用于索引的一个缺点是，它还在 B 树节点中存储了与特定键值对应的（指向包含键值的磁盘文件块的）数据指针。这种方法显著减少了能够装入 B 树节点中的项目数量，这导致 B 级树结构的增加和记录搜索时间的延长。通过仅在树的叶节点存储数据指针，B+ 树消除了上述缺点。

因此，B 树的内部节点和 B+ 树的叶节点具有非常不同的结构。应强调的是，由于数据指针仅存在于叶节点，所有键值及其相应的数据指针必须由叶节点存储，以便能够访问它们。此外，叶节点相互连接以提供对记录的有组织访问。因此，叶节点构成索引的第一级，内部节点是多级索引中的其他级别。

为了仅作为调节记录搜索的媒介，一些叶节点的键值也出现在内部节点中。与 B 树不同，B+ 树有两个阶，“a”和“b”，一个用于内部节点，另一个用于外部（或叶）节点。这一点从上面的描述中可以看出。具有“a”阶的内部 B+ 树具有以下节点结构

每个内部节点具有以下结构：其中每个 Ki 是键值对，每个 Pi 是树指针（指向树的另一个节点）（参见图 I）。
每个内部节点包含每个搜索字段以下值：K1 < K2 < …. < Kc-1
对于 Pi 指针指向的子树中每个搜索字段“X”的值，以下陈述成立：Ki-1 < X <= Ki，其中 1 < i < c，并且 Ki-1 < X。
每个内部节点最多包含“a”个树指针。
每个内部节点至少有 ceil(a/2) 个树指针，而根节点至少有两个树指针。
如果一个内部节点有“c”个指针，则它包含“c-1”个键值，其中 c< = a。

如果按顺序存储值，大多数查询可以更快地处理。然而，期望以排序的顺序一个接一个地存储表的行是不切实际的，因为这样做将需要为添加或删除的每一行重新创建表。

这促使我们考虑将我们的行放入树结构中。我们最初的想法是平衡二叉搜索树，如红黑树，但由于数据库存储在磁盘上，这实际上并没有多大意义。磁盘通过一次读取和写入大量数据来工作；这些块通常为 512 字节或四千字节。二叉搜索树的每个节点仅使用其中的一小部分。

找到一个更整齐地适合磁盘块的结构是有意义的。

这产生了 B+ 树，其中每个节点包含最多 d 个键和最多 d 个指向子节点的引用。每个引用指向一个子树的根，该子树的所有值都介于节点中的两个键之间，因此被认为是“介于”节点中的两个键之间。

这里有一个 d=4 的相对较小的树。

B+ 树的特性

只有叶节点可以存储数据点。
键存在于内部节点中。
我们在 B+ 树中使用键进行直接元素搜索。
如果有“m”个元素，则至少有“[m/2] -1”个键，最多有“m-1”个键。
根节点至少有两个子节点和一个键。
除了根节点外，每个节点可以有至少“m/2”个子节点，最多“m”个子节点（对于“m”个元素）。

B+ 树插入

在本教程中，您将了解 B+ 树的插入操作。此外，还提供了使用 C、C++、Java 和 Python 示例将成员插入 B+ 树。

向 B+ 树添加元素通常涉及三个基本步骤：找到正确的叶节点、添加元素以及平衡或拆分树。

下面我们详细考察这些情况。

插入操作

在将元素添加到 B+ 树之前，需要考虑这些特性。
根节点至少有两个子节点。
除根节点外，每个节点最多允许有 m 个子节点，最少有 m/2 个子节点。
每个节点至少有 m/2 - 1 个键，最多有 m - 1 个键。
插入元素的步骤如下。
转到正确的叶节点，因为每个元素都插入到叶节点中。
使用键激活叶节点。

情况 I

如果叶节点未满，则按升序将键插入叶节点。

情况 II

如果叶节点已满，则按升序将键插入每个叶节点，然后如下平衡树。
在 m/2 的位置拆分节点。
此外，将 m/2 键添加到父节点。
如果父节点已满，请遵循步骤二到三。

示例

显示插入后的树。

假设每个 B+ 树节点最多可存储 4 个指针和 3 个键

m=3（奇数），d=1
部分（针对奇数 m 值）
具有至少两个 (d+1) 个条目的叶节点
具有至少两个 (d+1) 个指针和一个条目的非叶节点
插入 1、3、5、7 和 9。
插入 1
插入 3、5
插入 7
插入 9

这是最终的 B+ 树。

C++ 程序

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
 
int bucketSize = 3;
 
// Create 2 classes, one for node and one for tree;
 
class node {
public:
    bool isLeaf;
    node** ptr;
    int *key, size;
    node();
};
node::node()
{
    key = new int[bucketSize];
    ptr = new node*[bucketSize + 1];
}
class Btree {
public:
    // Root of tree stored here;
    node* root;
    Btree();
    void deleteNode(int);
 
    int search(int);
    void display(node*);
    void insert(int);
    node* findParent(node*, node*);
    node* getRoot();
    void shiftLevel(int, node*, node*);
};
 
node* Btree::getRoot() { return root; }
Btree::Btree() { root = NULL; }
 
void Btree::insert(int x)
{
    if (root == NULL) {
        root = new node;
        root->key[0] = x;
        root->isLeaf = true;
        root->size = 1;
    }
 
    else {
        node* current = root;
        node* parent;
 
        while (current->isLeaf == false) {
            parent = current;
 
            for (int i = 0; i < current->size; i++) {
                if (x < current->key[i]) {
                    current = current->ptr[i];
                    break;
                }
 
                if (i == current->size - 1) {
                    current = current->ptr[i + 1];
                    break;
                }
            }
        }
 
        // now we have reached leaf;
        if (current->size
            < bucketSize) { // if the node to be inserted is
                            // not filled
            int i = 0;
 
            // Traverse btree
            while (x > current->key[i] && i < current->size)
                // goto pt where needs to be inserted.
                i++;
 
            for (int j = current->size; j > i; j--)
                // adjust and insert element;
                current->key[j] = current->key[j - 1];
 
            current->key[i] = x;
 
            // size should be increased by 1
            current->size++;
 
            current->ptr[current->size]
                = current->ptr[current->size - 1];
            current->ptr[current->size - 1] = NULL;
        }
 
        // if block does not have enough space;
        else {
            node* newLeaf = new node;
            int tempNode[bucketSize + 1];
 
            for (int i = 0; i < bucketSize; i++)
                // all elements of this block stored
                tempNode[i] = current->key[i];
            int i = 0, j;
 
            // find the right posn of num to be inserted
            while (x > tempNode[i] && i < bucketSize)
                i++;
 
            for (int j = bucketSize + 1; j > i; j--)
                tempNode[j] = tempNode[j - 1];
            tempNode[i] = x;
            // inserted element in its rightful position;
 
            newLeaf->isLeaf = true;
            current->size = (bucketSize + 1) / 2;
            newLeaf->size
                = (bucketSize + 1)
                  - (bucketSize + 1)
                        / 2; // now rearrangement begins!
 
            current->ptr[current->size] = newLeaf;
            newLeaf->ptr[newLeaf->size]
                = current->ptr[bucketSize];
 
            current->ptr[newLeaf->size]
                = current->ptr[bucketSize];
            current->ptr[bucketSize] = NULL;
 
            for (int i = 0; i < current->size; i++)
                current->key[i] = tempNode[i];
 
            for (int i = 0, j = current->size;
                 i < newLeaf->size; i++, j++)
                newLeaf->key[i] = tempNode[j];
 
            // if this is root, then fine,
            // else we need to increase the height of tree;
            if (current == root) {
                node* newRoot = new node;
                newRoot->key[0] = newLeaf->key[0];
                newRoot->ptr[0] = current;
                newRoot->ptr[1] = newLeaf;
                newRoot->isLeaf = false;
                newRoot->size = 1;
                root = newRoot;
            }
            else
                shiftLevel(
                    newLeaf->key[0], parent,
                    newLeaf); // parent->original root
        }
    }
}
 
void Btree::shiftLevel(int x, node* current, node* child)
{ // insert or create an internal node;
    if (current->size
        < bucketSize) { // if can fit in this level, do that
        int i = 0;
        while (x > current->key[i] && i < current->size)
            i++;
        for (int j = current->size; j > i; j--)
            current->key[j] = current->key[j - 1];
 
        for (int j = current->size + 1; j > i + 1; j--)
            current->ptr[j] = current->ptr[j - 1];
 
        current->key[i] = x;
        current->size++;
        current->ptr[i + 1] = child;
    }
 
    // shift up
    else {
        node* newInternal = new node;
        int tempKey[bucketSize + 1];
        node* tempPtr[bucketSize + 2];
 
        for (int i = 0; i < bucketSize; i++)
            tempKey[i] = current->key[i];
 
        for (int i = 0; i < bucketSize + 1; i++)
            tempPtr[i] = current->ptr[i];
 
        int i = 0, j;
        while (x > tempKey[i] && i < bucketSize)
            i++;
 
        for (int j = bucketSize + 1; j > i; j--)
            tempKey[j] = tempKey[j - 1];
 
        tempKey[i] = x;
        for (int j = bucketSize + 2; j > i + 1; j--)
            tempPtr[j] = tempPtr[j - 1];
 
        tempPtr[i + 1] = child;
        newInternal->isLeaf = false;
        current->size = (bucketSize + 1) / 2;
 
        newInternal->size
            = bucketSize - (bucketSize + 1) / 2;
 
        for (int i = 0, j = current->size + 1;
             i < newInternal->size; i++, j++)
            newInternal->key[i] = tempKey[j];
 
        for (int i = 0, j = current->size + 1;
             i < newInternal->size + 1; i++, j++)
            newInternal->ptr[i] = tempPtr[j];
 
        if (current == root) {
            node* newRoot = new node;
            newRoot->key[0] = current->key[current->size];
            newRoot->ptr[0] = current;
            newRoot->ptr[1] = newInternal;
            newRoot->isLeaf = false;
            newRoot->size = 1;
            root = newRoot;
        }
 
        else
            shiftLevel(current->key[current->size],
                       findParent(root, current),
                       newInternal);
    }
}
int Btree::search(int x)
{
    if (root == NULL)
        return -1;
 
    else {
        node* current = root;
        while (current->isLeaf == false) {
            for (int i = 0; i < current->size; i++) {
                if (x < current->key[i]) {
                    current = current->ptr[i];
                    break;
                }
 
                if (i == current->size - 1) {
                    current = current->ptr[i + 1];
                    break;
                }
            }
        }
 
        for (int i = 0; i < current->size; i++) {
            if (current->key[i] == x) {
                // cout<<"Key found "<<endl;
                return 1;
                // return;
            }
        }
 
        // cout<<"Key not found"<<endl;
        return 0;
    }
}
 
// Print the tree
void Btree::display(node* current)
{
    if (current == NULL)
        return;
    queue<node*> q;
    q.push(current);
    while (!q.empty()) {
        int l;
        l = q.size();
 
        for (int i = 0; i < l; i++) {
            node* tNode = q.front();
            q.pop();
 
            for (int j = 0; j < tNode->size; j++)
                if (tNode != NULL)
                    cout << tNode->key[j] << " ";
 
            for (int j = 0; j < tNode->size + 1; j++)
                if (tNode->ptr[j] != NULL)
                    q.push(tNode->ptr[j]);
 
            cout << "\t";
        }
        cout << endl;
    }
}
 
node* Btree::findParent(node* current, node* child)
{
    node* parent;
    if (current->isLeaf || (current->ptr[0])->isLeaf)
        return NULL;
 
    for (int i = 0; i < current->size + 1; i++) {
        if (current->ptr[i] == child) {
            parent = current;
            return parent;
        }
        else {
            parent = findParent(current->ptr[i], child);
            if (parent != NULL)
                return parent;
        }
    }
    return parent;
}
 
signed main()
{
    ios_base::sync_with_stdio(false);
    Btree node;
    cout << "The size of bucket is " << bucketSize << "! "
         << endl;
 
    node.insert(1);
    node.insert(2);
    node.insert(3);
    node.display(node.getRoot());
    node.insert(4);
    node.insert(5);
    node.display(node.getRoot());
 
    return 0;
}

输出

The size of bucket is 3! 
1 2 3     
3     
1 2     3 4 5

B+ 树的优点

与具有相同层数的 B 树相比，B+ 树可以在其内部节点中存储更多条目。这强调了每个特定键的搜索时间有了多么大的改进。由于其较低的层数和 Pnext 指针，B+ 树在从驱动器访问记录方面特别快速和有效。
B+ 树允许数据进行顺序访问和直接访问。
要获取记录，需要相同数量的磁盘访问。
由于 B+ 树中的冗余搜索键，不可能再次存储搜索键。

B+ 树的缺点

按顺序访问键的难度是 B 树的主要缺点。B+ 树仍然具有快速的随机访问。

B+ 树的应用

多级索引
更快的树操作（插入、删除、搜索）
数据库索引

B 树与 B+ 树

以下是 B 树和 B+ 树之间的一些区别

数据和搜索键存储在 B 树的内部节点或叶节点中。但是，数据仅存储在 B+ 树的叶节点中。
由于所有数据都位于 B+ 树的叶节点中，因此搜索任何数据都非常简单。在 B 树的叶节点中无法找到数据。
数据可以位于 B 树的内部节点或叶节点中。内部节点删除非常困难。数据仅存在于 B+ 树的叶节点中。叶节点删除相对简单，因为可以直接删除。
B 树的插入比 B+ 树更复杂。
B+ 树存储冗余搜索键，但 B 树没有冗余值。
在 B+ 树中，叶节点数据按顺序链接列表排序，但在 B 树中，叶节点不能使用链表存储。许多数据库系统的实现更倾向于 B+ 树的结构简洁性。

基本区别在于它们如何利用内部存储。

概述

B+ 树是一种非线性存储结构，用于存储具有“一对多”关系的数据元素集合，通常用于数据库和操作系统文件系统。

非叶节点不存储数据，只存储索引（冗余），可以放置更多索引。
叶节点包含所有索引字段。
叶节点通过指针链接以提高区间访问性能。

为什么选择 B+ 树？

由于 MySQL 通常将数据存储在磁盘上，读取数据会产生磁盘 IO 消耗。B+ 树的非叶节点不存储数据。通常，节点的大小设置为磁盘页面大小，因此B+ 树的每个节点可以容纳更多键，并且 B+ 树的高度较低，从而减少了磁盘 IO 消耗。
B+ 树叶节点形成一个链表，并用于范围搜索和排序。

MySQL 使用 B+ 树作为索引

由于 MySQL 通常将数据存储在磁盘上，读取数据会产生磁盘 IO 消耗。B+ 树的非叶节点不存储数据，但 B 树的非叶节点会存储数据。通常，节点的大小会设置为磁盘页面大小，以便 B+ 树的每个节点可以容纳更多键，而 B 树的键较少。因此，B 树的高度将高于 B+ 树，这将导致更多的磁盘 IO 消耗。
B+ 树叶节点形成一个链表，并用于范围搜索和排序。B 树的范围搜索和排序需要递归遍历树。

下一个主题检查二叉树中的镜像图像

B+ 树插入

B+ 树的特性

B+ 树插入

插入操作

示例

C++ 程序

B+ 树的优点

B+ 树的缺点

B+ 树的应用

B 树与 B+ 树

概述

为什么选择 B+ 树？

MySQL 使用 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+ 树插入

B+ 树的特性

B+ 树插入

插入操作

示例

C++ 程序

B+ 树的优点

B+ 树的缺点

B+ 树的应用

B 树与 B+ 树

概述

为什么选择 B+ 树？

MySQL 使用 B+ 树作为索引

相关帖子

第 k 大的连续子数组和

矩阵中最优单元以收集最多金币

根据军衔查找士兵完成的任务

AVL 树的时间复杂度

检测并移除链表中的循环

二叉树的底视图

合并两个二叉最大堆

查找二叉树节点层级的公式

Tarjan 算法用于查找强连通分量

将中缀表达式转换为后缀表达式

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器