【数据结构】B树

1 B树介绍

B���（英语：B-tree），是一种在计算机科学自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉搜索树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。B树减少定位记录时所经历的中间过程，从而加快访问速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

那为什么要使用 B-树呢（或者说为啥要有 B-树呢）？

要解释清楚这一点，我们假设我们的数据量达到了亿级别，主存当中根本存储不下，我们只能以块的形式从磁盘读取数据，与主存的访问时间相比，磁盘的 I/O 操作相当耗时，而提出 B-树的主要目的就是减少磁盘的 I/O 操作。大多数平衡树的操作（查找、插入、删除，最大值、最小值等等）需要 O(ℎ) 次磁盘访问操作，其中 ℎ 是树的高度。但是对于 B-树而言，树的高度将不再是logn(其中 n是树中的结点个数），而是一个我们可控的高度 ℎ （通过调整 B-树中结点所包含的键【你也可以叫做数据库中的索引，本质上就是在磁盘上的一个位置信息】的数目，使得 B-树的高度保持一个较小的值）。一般而言，B-树的结点所包含的键的数目和磁盘块大小一样，从数个到数千个不等。由于B-树的高度 h 可控（一般远小于logn ），所以与 AVL 树和红黑树相比，B-树的磁盘访问时间将极大地降低。

平衡二叉排序树是利用插入的成本缓解查找效率---------->红黑树来解决（最长子树不超过最短子树的2倍。数据量大的时候，树会很深，查找次数变多）----------->B树（多叉，多路查找树）

动画显示树调整的网站：Data Structure Visualization

2 B树特点

B树是一种平衡的多叉树，通常我们说m阶的B树，它必须满足如下条件：

• 每个节点最多有m个子节点。
• 每一个非叶子节点（除根节点）最少有[m/2]个子节点。
• 如果根节点不是叶子节点，那么它至少有两个子节点。
• 有k个子节点的非叶子节点拥有k-1个键，且升序排列，满足k[i]
• 每个节点至多包含2*k-1个键。
• 所有的叶子节点都在同一层。
• 像其他平衡的二叉搜索树一样，搜索插入和删除的时间复杂度是O(logn)
• 每个节点的结构是：

  其中：

  n记录这个节点关键字的个数；

  P0存储的是第一个孩子的地址，P1存储的是第二个孩子的地址，以此类推。。。。。。

  K1是第一个关键字，K2是第二个关键字，以此类推。。。。。。

  B树中一个节点的子节点数目的最大值，用m表示，假如最大值为4，则为4阶，如下图

  有三个子节点，所以是4阶

  性质：

  • 每个节点最多有m个子节点。
  • 每一个非叶子节点（除根节点）最少有[m/2]个子节点。
  • 如果根节点不是叶子节点，那么它至少有两个子节点。
  • 有k个子节点的非叶子节点拥有k-1个键，且升序排列，满足k[i]
  • 每个节点至多包含2*k-1个键。
  • 所有的叶子节点都在同一层。
  • 满足n叉排序树

    3 B树的增删改查

    磁盘预读

    内存跟磁盘发生数据交互的时候，一般情况下有一个最小的逻辑单元，称之为页,datapage

    页一般由操作系统决定是多大，一般是4k或者8k，我们在数据交互时，可以取页的整数倍来进行读取。

    电脑的文件都是datapage的整数倍
    

    每个节点放在磁盘块里，用B树做索引，这个磁盘大小是16k

    三层数据。

    对比B树和B+树

    有一个很重要的不同是：B+树的数据都存在叶子节点上。

    3.3 B树的查找

    查找简单，将查找放到前面。。。。。。

    B树的查找操作与二叉排序树（BST）极为类似，只不多B树中的每个结点包含多个关键字。假设待查找的关键字为K，从根结点开始，递归向下进行查找。对每一个访问的非叶子结点，如果结点包含待查找的关键字K，则返回结点指针；否则，递归到该结点的恰当子代（该子代结点中的关键字均在比K更大的关键字之前）。如果抵达了叶子结点且没有找到K则返回 null。

    如图，简化画出来。查找关键字F为例进行说明

    第一步：访问根结点P，发现关键字F小于P ，则查找结点P的左孩子。

    第二步：访问结点 P 的左子结点【C、G、L】 ，对于一个结点中包含多个关键字时，顺序进行访问，首先与关键字C进行比较，发现比C大；然后与关键字G进行比较，发现比G小，则说明待查找关键字F位于关键字C和关键字G之间的子代中。

    第三步：访问关键字C和关键字G之间的子代，该子代结点包含三个关键字【D、E、F】，进行顺序遍历，比较关键字D和F，F比D大

    顺序访问关键字E，F比E大：

    顺序访问关键字F，发现与待查找关键字相同，查找成功。则返回结点【D、E、F】的指针。

    接下来定义一个B树的节点

    // B 树的节点class BTreeNode {public:    vector keys;               // 存储节点的键    int degree;                     // 节点的度（最大子节点数量）    vector children;    // 存储子节点的指针    bool leaf;                      // 标志节点是否为叶节点    // 构造函数    BTreeNode(int degree, bool leaf);    // 遍历节点    void traverse();    // 在节点及其子树中搜索给定的键    BTreeNode* search(int key);    // 在非满节点中插入键    void insertNonFull(int key);    // 分裂满子节点    void splitChild(int i, BTreeNode* y);};// BTreeNode 类构造函数实现BTreeNode::BTreeNode(int degree, bool leaf) {    this->degree = degree;    this->leaf = leaf;    keys.reserve(2 * degree - 1);  // 为键分配内存    children.reserve(2 * degree);  // 为子节点指针分配内存}// 从左到右遍历节点的键，并在需要时递归遍历子树void BTreeNode::traverse() {    int i;    for (i = 0; i traverse();}// 打印键值        cout  keys[i]) {    i++;}    // 键在当前节点中找到    if (keys[i] == key) {    return this;}    // 当前节点为叶节点且未找到键    if (leaf == true) {    return nullptr;}// 递归搜索子树    return children[i]->search(key);}

    这段代码笔者使用chatGPT生成的

    （1）节点有个属性是节点的度，即每个节点最多有m个子节点。

    （2）traverse函数是：左到右遍历节点的键，并在需要时递归遍历子树

    （3）search函数是：在节点及其子树中搜索给定的键

    // 在节点及其子树中搜索给定的键BTreeNode* BTreeNode::search(int key) {    int i = 0;    // 因为一个节点存储的数据是有序的    while (i  keys[i]) {    i++;}    // 键在当前节点中找到    if (keys[i] == key) {    return this;}    // 当前节点为叶节点且未找到键    if (leaf == true) {    return nullptr;}// 递归搜索子树    return children[i]->search(key);}

    （4）insertNonFull和splitChild先略过

    然后是B树代码

    // B 树class BTree {public:    BTreeNode* root;    // B 树的根节点    int degree;         // B 树的度    // 构造函数    BTree(int degree);    // 遍历整棵树    void traverse();    // 在树中搜索给定的键    BTreeNode* search(int key);    // 向树中插入键    void insert(int key);};// BTree 类的实现BTree::BTree(int degree) {    root = nullptr;    this->degree = degree;}// 遍历整棵树void BTree::traverse() {    if (root != nullptr) {    root->traverse();}}// 在树中搜索给定的键BTreeNode* BTree::search(int key) {    return (root == nullptr) ? nullptr : root->search(key);}

    整棵B树的查找

    // 在树中搜索给定的键BTreeNode* BTree::search(int key) {    return (root == nullptr) ? nullptr : root->search(key);}

    3.2 B树的中序遍历

    B-树的中序遍历与二叉树的中序遍历也很相似，从最左边的孩子结点开始，递归地打印最左边的孩子结点，然后对剩余的孩子和关键字重复相同的过程。最后，递归打印最右边的孩子。

    一定要注意，本应该是26个字母，但是这里缺少了字母I，之后看插入操作时可以将其插入。

    void BTreeNode::inOrderTraversal() {    int i;    for (i = 0; i inOrderTraversal();}        cout inOrderTraversal();}}

    3.3 B树的插入

    一个新插入的关键字K，总是被插入到叶子结点。

    与二叉排序树的插入操作类似，从根结点开始，向下遍历直到叶子结点，到达叶子结点，将关键字K插入到相应的叶子结点。

    与 BST 不同的是，通过最小度定义了一个结点可以包含关键字的个数的一个取值范围，所以在插入一个关键字时，就需要确认插入关键字之后结点是否超出结点本身最大可容纳的关键字个数。

    如何判断在插入一个关键字 k 之前，一个结点是否有可供当前结点插入的空间呢？

    可以使用一个称为splitChild()的操作实现，即拆分一个结点的孩子。下图中，X的孩子结点Y被拆分成了两个结点Y和Z。拆分操作将一个关键I上移，并以上移的关键I对结点Y进行拆分，拆分成包含关键字【G、H】 的结点Y和包含关键字【J、K】的结点Z。这一过程又称之为 B树的生长，区别于 BST 的向下生长。

    综上，B树在插入一个新的关键字K时，我们从根结点一直访问到叶子结点，在遍历一个结点之前，首先检查这个结点是否已经满了，即包含了2*k-1个关键字，如果结点已满，则将其拆分并创建新的空间。插入操作的伪代码描述如下：

    插入操作伪码

    • 初始化 x 作为根结点
    • 当 x 不是叶子结点，执行如下操作：
      • 找到 x 的下一个要被访问的孩子结点 y
      • 如果 y 没有满，则将结点 y 作为新的 x
      • 如果 y 已经满了，拆分 y ，结点 x 的指针指向结点 y 的两部分。 如果 k 比 y 中间的关键字小， 则将 y 的第一部分作为新的 x ，否则将 y 的第二部分作为新的 x ，当将 y 拆分后，将 y 中的一个关键字移动到它的父结点 x 当中。
    • 当 x 是叶子结点时，第二步结束； 由于我们已经提前查分了所有结点，x 必定至少有一个额外的关键字空间，进行简单的插入即可。

      事实上 B树的插入操作是一种主动插入算法，因为在插入新的关键字之前，会将所有已满的结点进行拆分，提前拆分的好处就是，不必进行回溯，遍历结点两次。如果我们不事先拆分一个已满的结点，而仅仅在插入新的关键字时才拆分它，那么最终可能需要再次从根结点出发遍历所有结点，比如在我们到达叶子结点时，将叶结点进行拆分，并将其中的一个关键字上移导致父结点分裂（因为上移导致父结点超出可存储的关键字的个数），父结点的分裂后，新的关键字继续上移，将可能导致新的父结点分裂，从而出现大量的回溯操作。但是 B-树这种主动插入算法中，就不会发生级联效应。当然，这种主动插入的缺点也很明显，我们可能进行很多不必要的拆分操作。

      插入操作案例

      上图中插入关键字I为例进行说明。其中最小度K=2，一个结点最多可存储2K-1=3个结点。

      • 每个节点最多有m个子节点。
      • 每一个非叶子节点（除根节点）最少有[m/2]个子节点。
      • 如果根节点不是叶子节点，那么它至少有两个子节点。
      • 有k个子节点的非叶子节点拥有k-1个键，且升序排列，满足k[i]
      • 每个节点至多包含2*k-1个键。

        第一步：访问根结点，发现插入关键字I小于P, 但根结点未满，不分裂，直接访问其第一个孩子结点。

        第二步：访问结点P的第一个孩子结点【C、G、L】 ，发现第一个孩子结点已满，将第一个孩子结点分裂为两个：

        第三步：将结点I插入到结点L的第一个左孩子当中，发现L的第一个左孩子【H、J、K】已满，则将其分裂为两个。

        第四步：将结点I插入到结点J的第一个孩子当中，发现L的第一个孩子结点【H】未满且为叶子结点，则将I直接插入。

        代码

        // 在非满节点中插入键void BTreeNode::insertNonFull(int key) {    int i = keys.size() - 1;    if (leaf) {        keys.push_back(0);        while (i >= 0 && key = 0 && key keys.size() == 2 * degree - 1) {            splitChild(i + 1, children[i + 1]);   // 分裂满子节点            if (key > keys[i + 1])                i++;        }        children[i + 1]->insertNonFull(key);      // 递归插入    }}// 分裂满子节点void BTreeNode::splitChild(int i, BTreeNode* y) {    BTreeNode* z = new BTreeNode(y->degree, y->leaf);   // 创建新节点    z->keys.resize(degree - 1);                         // 调整新节点的键数组大小    for (int j = 0; j keys[j] = y->keys[j + degree];               // 复制 y 的后半部分键到 z    if (!y->leaf) {        z->children.resize(degree);                     // 调整新节点的子节点数组大小        for (int j = 0; j children[j] = y->children[j + degree];   // 复制 y 的后半部分子节点到 z    }    y->keys.resize(degree - 1);                         // 调整 y 的键数组大小    children.insert(children.begin() + i + 1, z);        // 将新节点插入当前节点的子节点中    keys.insert(keys.begin() + i, y->keys[degree - 1]); // 将 y 的中间键插入当前节点的键中}// 向树中插入键void BTree::insert(int key) {    if (root == nullptr) {        // 如果树为空，则创建一个只包含一个键的根节点        root = new BTreeNode(degree, true);        root->keys.push_back(key);    } else {        // 如果根节点满，则树长高，需要分裂根节点        if (root->keys.size() == 2 * degree - 1) {            BTreeNode* s = new BTreeNode(degree, false); // 创建一个新的根节点            s->children.push_back(root);                // 将现有根节点作为 s 的子节点            s->splitChild(0, root);                     // 分裂根节点            int i = 0;            if (s->keys[0] children[i]->insertNonFull(key);         // 递归插入键            root = s;                                    // 更新树的根节点        } else            root->insertNonFull(key);                    // 否则，在根节点中插入键    }}

        3.4 B树的删除

        B树的删除操作相比于插入操作更为复杂，如果仅仅只是删除叶子结点中的关键字，也非常简单，但是如果删除的是内部节点的，就不得不对结点的孩子进行重新排列。

        与 B树的插入操作类似，我们必须确保删除操作不违背 B树的特性。正如插入操作中每一个结点所包含的关键字的个数不能超过2t-1一样，删除操作要保证每一个结点包含的关键字的个数不少于t-1个（除根结点允许包含比t-1少的关键字的个数。

        初始的 B树如图所示，其中最小度t=3每一个结点最多可包含 5 个关键字，至少包含 2个关键字（根结点除外）。

        • 每个节点最多有m个子节点。
        • 每一个非叶子节点（除根节点）最少有[m/2]个子节点。
        • 如果根节点不是叶子节点，那么它至少有两个子节点。
        • 有k个子节点的非叶子节点拥有k-1个键，且升序排列，满足k[i]
        • 每个节点至多包含2*k-1个键。

          1. 待删除的关键字key在结点 x 中，且 x 是叶子结点，删除关键字F

          2. 待删除的关键字key在结点 x 中，且 x 是内部结点，分一下三种情况

          4 B+树

          B+树是应文件系统所需而产生的B树的变形树，那么可能一定会想到，既然有了B树，又出一个B+树，那B+树必然是有很多优点的

          B+树的特征：

          • 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；
          • 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
          • 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；

            为什么说B+树比B树更适合数据库索引？

            1）B+树的磁盘读写代价更低

            　　B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了；

            2）B+树查询效率更加稳定

            　　由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当；

            3）B+树便于范围查询（最重要的原因，范围查找是数据库的常态）

            　　B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题，正是为了解决这个问题，B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低；不懂可以看看这篇解读-》范围查找

            参考：

            [1] https://zh.wikipedia.org/zh-hans/B%E6%A0%91

            [2] 图解：什么是B树？（心中有 B 树，做人要虚心）一文读懂B-树 - 知乎 (zhihu.com)

            [3] B 树 - OI Wiki (oi-wiki.org)

            [4] 终于把B树搞明白了(四)_B树的删除操作_哔哩哔哩_bilibili

            [5] notes/docs/B树和B+树详解.md at master · wardseptember/notes · GitHub

            [6] https://www.cnblogs.com/lianzhilei/p/11250589.html