B树

B树

B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

性质(m>2)

假设一个节点存储元素个数为x

  • 根节点中的元素数：1<=x<=m-1

  • 非根节点的元素数：ceil(m/2) - 1 <= x <= m-1

  • 如果有子节点，子节点个数 y=x+1

    • 根节点的子节点数 2<=y<=m

    • 非更节点子节点数 ceil(m/2)<=y<=m

m=3, 2<=y<=3, 称为(2,3)树，2-3树

m=4, 2<=y<=4, 称为(2,4)树，2-4树

依次类推..

如图是一张m=4的B数:

b_tree_01

B树和二叉搜索树

B树和二叉搜索树，在逻辑上是等价的

二叉搜索树多代节点合并，可以获得一个超级节点

  • 2代合并的超级节点，最多拥有4个子节点(至少是4阶B树)

  • 3代合并的超级节点，最多拥有8个子节点(至少是8阶B树)

  • n代合并的超级节点，最多拥有2^n个节点(至少是2^n阶B树)

搜索

跟二叉树搜索类似

  1. 先在节点内部从小到大搜索元素
  2. 如果命中，搜索结束
  3. 未命中，再去对应的子节点中搜索元素，重复步骤1

添加

新添加的元素必定是添加到叶子节点

如果叶子节点超过限制，则取中间节点上溢，上溢后父节点如超过限制，则再次上溢。

下面是往B树中依次插入6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4的演示动画：

img

删除

  • 如果需要删除的元素在叶子节点中直接删除即可

  • 如果需要删除的元素在非叶子节点

    1. 先找到前驱或后继元素，覆盖所需删除元素的值
    2. 再把前驱或后继元素删除

    非叶子节点的前驱或后继元素，必定再叶子节点中

真正删除的元素都是发生在叶子节点中

下溢

叶子节点中被删掉一个元素后，元素个数可能会低于最低限制floor(m/2)-1，这种现象称为下溢。

下溢节点的元素数量必须等于floor(m/2)-2

  • 如果下溢节点临近的兄弟节点有至少floor(m/2)个元素，可以向其借一个元素

    1. 将父节点的一个临近下溢节点的元素插入到下溢节点的0位置(最小位置)
    2. 用兄弟节点的元素替代腹肌诶单的元素

    这种操作其实就是旋转

  • 如果临近的兄弟节点只有floor(m/2)个元素

    1. 将父节点中两个子节点中间的元素挪下来跟左右子节点合并
    2. 合并后的节点元素个数等于(floor(m/2) - 1) + 1 + floor(m/2) - 2 = m - 2个
    3. 如果父节点下溢，则按照1方法向上传播