Mcginn's Blog

B-Tree

2019/07/22

简介

简单来说,B-Tree 是针对大数据存取的平衡树,考虑了磁盘读取对查找效率的影响。

B-Tree 的主要思想是通过减少磁盘读取次数来提高数据存取性能,而磁盘读取次数与树高相关。故B-Tree 允许每个节点拥有多于 2 个的子节点来减小树高。

与二叉平衡树类似,B-Tree 中的每个节点存储若干键值(keys)以及子节点地址。

图 1. B-Tree 结构图

定义和性质

阶(order):将子节点的允许最大数量定义为阶,如图 1 为 5 阶树。

阶的 B-Tree 满足以下定义:

  1. 每个节点最多能有 个子节点。
  2. 每个内部节点至少有 个子节点,内部节点(Internal nodes)为除根节点和叶节点以外的节点。
  3. 拥有 个子节点的非叶节点存有 个键值。
  4. 每个节点中的键值按递增排序。
  5. 所有的叶节点高度一样。

操作

对于平衡🌳的操作主要就是插入(Insertion)删除(Deletion)

以下操作均基于键值两两不同的假设进行讨论,同时键值的数量范围定义为 ,阶

插入

首先找到键值归属的叶节点,插入到该节点中,节点的键值数量可能超过上限 ,即当前键值数量为

此时用中位数将该节点划分成两个新的节点,每个新节点含有 个键值,如图 2 所示。

之后将键值中位数插入到父节点中,父节点的键值数量 +1,也有可能超上限,故需要迭代更新。

图 2. 节点分裂

删除

主要思路

将内部节点中的删除操作转移至叶节点中,然后自下而上重新平衡,达到键值数量要求。

叶节点

直接将对应的键值删除即可。

内部节点

假设当前删除键值为 ,则 的前继 为左子树中的最大键值,后继 为右子树中的最小键值。

均可替代 作为分割左、右子树的新键值,同时这两个键值必然在叶节点中,进而将删除操作转移到叶节点中。

重平衡

在叶节点删除键值后可能出现键值数量为 导致下溢出。此时通过转移兄弟节点的键值来完成键值补充,主要分两种情况:

  1. 合并:当前节点的左、右兄弟节点均只有 个键值,此时可与其中一个兄弟节点及父节点中的分割键值合并,新节点的键值数量为 ,相当于节点分裂的逆操作。此时父节点的键值数量减 1,需要迭代重平衡。

    图 3. 节点合并

  2. 旋转:假设右兄弟节点的键值大于 个(左兄弟同理),将父节点的分割键值插入到当前节点中,右兄弟节点的第 1 个键值插入到父节点中。此时当前节点、兄弟节点和父节点的键值数量均满足键值数量要求,完成平衡操作。

    图 4. 旋转操作

参考

  1. wikipeadia
  2. geeksforgeeks
CATALOG
  1. 1. 简介
  2. 2. 定义和性质
  3. 3. 操作
    1. 3.1. 插入
    2. 3.2. 删除
      1. 3.2.1. 主要思路
      2. 3.2.2. 叶节点
      3. 3.2.3. 内部节点
      4. 3.2.4. 重平衡
  4. 4. 参考