JZTXT

查找 - B-树 & B+树

发布时间 2023-12-03 12:25:28作者: ww0809

B-树

定义

B-树也叫B树、B_树（“-”是个连字符，不是“减”），是适用于外查找（存在外存里的）的平衡多叉查找树。
适用于磁盘目录管理、数据库系统索引等。

  1. 每个结点至多有m棵子树（m称为阶，m等于2时B-树就是二叉搜索树）。阶数通常非常大，以保证在存了大量数据的情况下，树的高度不会过于大。
  2. 如果根不是叶子，则至少有两棵子树。
  3. 除根之外的所有非叶子结点至少有ceil(m/2)棵子树。
  4. 失败结点：叶子结点。所有叶子结点都位于同一层。
  5. 非叶子结点最多有(m-1)个关键字。（之所以这样要求，是因为B-树的每个结点其实可以理解成关键字“填补了”子树的缝隙，子树存在于两个相邻关键字之间（自己瞎理解的，如果让你感到迷惑就忽略吧））

特点

  1. 平衡：所有叶子都在同一层。
  2. 有序：左小右大。
  3. 多路：非叶子节点有多个关键字和子树。

查找

存储结构

#define m 3
typedef struct BTNode {
    int keynum;
    struct BTNode *parent;
    int k[m + 1]; // 关键字
    struct BTNode *ptr[m + 1]; // 子树指针
    Record *recptr[m + 1]; 
} BTNode, *BTree;
typedef struct {
    BTNode *pt;
    int i; // 关键字序号
    int tag; // 查找是否成功
} Result;

算法描述

顺序/折半查找，将待查值与根节点各个关键字比较。

  • key == Ki 查找成功。
  • key < K1 沿第一个子树向下找。
  • Ki < key < K(i+1) 沿着第i个子树向下找。
  • key > Kj 沿着随后一个子树指针向下找。

如果直到叶子节点也没有找到，则查找失败。

PS：“关键字”指的并不是存储的数据，实际上一个结点中存储的应该是很多个<key, value>键值对，只是为了方便而用关键字来代指键值对。所以在查找、插入、删除的过程中，真正操作的对象其实是“记录”，也就是键值对。

算法实现

Result SearchBTree(BTree T, int key) {
    p = T, q = NULL, found = false, i = 0;
    while(p && !found) {
        i = Search(p, key);
        if(i > 0 && p->k[i] == key) found = true;
        else q = p, p = p->ptr[i];
    }
    return (found) ? (p, i, 1) : (q, i, 0);
}

算法分析

B-树查找的两种基本操作是在树上找结点和在结点中找关键字。由于B-树通常存在磁盘上，所以前者是在磁盘上执行的，后者是在内存中执行的。所以磁盘中的查找次数，也就是待查关键字在B-树上的层数（深度）决定了查找效率。
查找可能在非叶子结点结束，整棵树中查找一次的效率逼近二分查找。

插入

算法描述

  • 如果待插入key存在，就用新的value替换旧的value。
  • 如果待插入key不存在，就在叶子结点中插入；插入之后判断当前结点key数是否小于等于m-1，如果不满足，则取当前结点的中间结点（如果是偶数就取中间左侧或右侧任意一个结点）放到其上一层结点的正确位置，也就是“结点分裂”。

算法分析

如果所有关键字都事先排序后再插入，会导致结点空间利用率很低，最差只有50%（因为父结点对应关键字与其右侧关键字之间的整数个数可能小于子结点的空间，比如父节点27与30之间的子树，最多只能有28和29两个结点，而空间很可能大于2）。

删除

算法描述

  1. 如果待删结点位于非叶子结点，先将其替换到叶子中再进行删除。
  2. 删除之后判断当前结点中关键字个数是否大于等于ceil(m/2)-1，如果是就结束操作。
  3. 如果不是，先看其兄弟结点是否可以对其进行支援（挪过一个关键字并不影响兄弟结点自身的合法性），如果可以就做，如果不可以，从其父结点中取出关键字并与其及其兄弟结点进行结点合并。

B+树

B+树与B树的区别

  1. B+树的非叶子结点只存储关键字，不存储数据，可以减少结点数从而减小树的高度，进而查找过程中需要进行的磁盘操作次数就更少。
  2. B+树的叶子结点按照从小到大的顺序依次连接。
  3. B+树除根之外的所有非叶子结点至少有ceil(m/2)个关键字（注意B树除根之外的所有非叶子结点至少有ceil(m/2)棵子树）。

查找

与B-树类似，只是如果非叶子结点上的关键字等于待查关键字，不会终止查找，而是继续向下直到找到对应的叶子结点。也就是说，不会像B-树一样时间效率不稳定。由于B+树所有叶子都位于同一高度，所以查找的时间复杂度稳定在O(logn)。

插入和删除

都只在叶子结点中进行。如果插入/删除之后导致出现溢出/关键字不够，就操作对应结点及其兄弟/父结点进行结点分裂/合并。

为什么用B+树而不用B树？

  1. IO次数更少。每个结点能存的关键字数量更多，所以高度更低，需要的磁盘IO次数更少。
  2. 便于范围查询。只需要扫描一遍所有叶子就可以完成给定上下限的范围查询，而B树需要进行中序遍历。
  3. 查询效率更稳定。由于每次查询都是从根到叶子，所以查询复杂度稳定为树的高度。