概述

B 树是多路平衡树。一棵 m 阶 B 树需要满足如下性质：

• 每个节点最多有 m - 1 个关键字

• 根节点最少有 1 个关键字

• 除根节点外，每个节点最少有 ceil(m / 2) - 1 个关键字

• 所有叶子节点出现在同一层

• 节点的子树数量比关键字数量多 1。每个节点形如：(P₀, K₀, P₁, ..., P_i, K_i, P_i+1, ..., K_n-1, P_n)，其中：

  • ceil(m / 2) - 1 <= n <= m - 1
  • P_i 所指向的子树中的所有节点的关键字都不大于 K_i
  • P_i+1 所指向的子树中的所有节点的关键字都不小于 K_i
  • K_i 不大于 K_i+1

接下来分析一棵有 n 个关键字的 m 阶 B 树的最大深度和最小深度：

• 当根节点只有 1 个关键字，其它节点都只有 ceil(m / 2) - 1 个关键字时，B 树的深度最大
  设树的深度是 h，则左右子树的深度都是 h - 1
  设j = ceil(m / 2) - 1
  那么左子树和右子树的关键字数量都是：
  j + (j+1)×j + (j+1)²×j + ... + (j+1)^h-2×j
  根据等比数列的求和公式，得到左子树和右子树的关键字数量都是 (j+1)^h-1 - 1
  即 n = 1 + 2 × ((j+1)^h-1 - 1) ===>
  h = log_ceil(m/2)((n+1)/2) + 1
• 当每个节点都有 m - 1 个元素时，B 树的深度最小
  设j = m - 1、树深为 h
  则 j + (j+1)×j + ... + (j+1)^h-1×j = n
  根据等比数列的求和公式，得到 n = (j+1)^h - 1 ===>
  h = log_ceil(m/2)(n+1)

B 树的深度直接影响插入节点、查找节点、删除节点的时间复杂度。

插入关键字

1，如果树为空，那么创建根节点，然后退出

2.1， 否则，令临时指针 node 指向根节点

2.2，设node 的关键字列表为 keywords、孩子节点列表为 children、keywords 的长度为 length，并执行下面的过程：

• 查找插入位置 pos

  • 如果 keyword <= keywords[0]，那么 pos = 0
  • 如果 keyword >= keywords[length - 1]，那么 pos = length
  • 如果 keywords[index] <= keyword <= keywords[index + 1]，那么 pos = index + 1

• 如果 children[pos] 不是根节点，那么令 node = children[pos]，然后回到步骤 2.2

• 否则，在 keywords 中的索引为 pos 的位置之前插入 keyword

3，如果 node 的关键字个数超过 m - 1，则执行下面的流程：

• 设 mid = m / 2、node 的关键字列表中索引为 mid 的分量为 mid_keyword，在 mid 处将节点一分为二：node、new_node
• 如果 node 是根节点，那么创建新的根节点，并将 node 和 new_node 分别作为其左、右孩子节点，然后退出
• 设 node 的父节点是 parent，node 在 parent 的孩子节点列表中的索引是 index，并在 parent 的关键字列表中索引为 index 的位置之前插入 mid_keyword；在 parent 的孩子节点列表中索引为 index + 1 的位置之前插入 new_node
• 令 node = parent，然后回到步骤 3

查找关键字

B 树的查找是一个交叉查找的过程，其过程如下：

1，如果树为空，那么查找失败

2.1，否则，令临时指针 node 指向根节点

2.2，执行下面的过程：

• 设 node 的关键字列表为 keywords、孩子节点列表为 children、keywords 的长度为 length

• 如果 keyword == keywords[index]，那么查找成功，返回 node、index

• 如果 node 是叶子节点，那么查找失败

• 否则

  • 如果 keyword < keywords[0]，则令 node = children[0]
  • 如果 keyword > keywords[length - 1]，则令 node = children[length]
  • 如果 keywords[index] < keyword < keywords[index + 1]，则令 node = children[index + 1]
  • 回到步骤 2.2

删除关键字

1， 找到待删除关键字 (deleted_node, deleted_index)

2，查找“真正”删除的节点和位置 (node, index)

• 如果 deleted_node 不是叶子节点，那么使用 deleted_node.children[deleted_index + 1] 的最左关键字 (node, index) 代替待被删除的关键字（也可以使用 deleted_node.children[deleted_index] 的最右关键字代替待被删除的关键字）
• 否则，令 node = deleted_node、index = deleted_index

3， 移除 node 中索引为 index 的关键字

4， 如果 node 是根节点

• 并且删除关键字后，节点没有关键字了，那么将树置空，然后退出
• 否则直接退出，因为根节点没最少关键字个数的限制

5，如果 node 的关键字个数小于 ceil(m / 2) - 1，那么按照如下的方式进行调整

• 找到node 的父节点、左兄弟、右兄弟

• 如果左兄弟非空，且关键字个数大于 ceil(m / 2) - 1，那么从左兄弟借一个关键字，然后退出

  • 需要通过父节点进行中转

• 如果右兄弟非空，且关键字个数大于 ceil(m / 2) - 1，那么从右兄弟借一个关键字，然后退出

  • 需要通过父节点进行中转

• 否则，如果有左兄弟，则与父节点、左兄弟进行三方合并；如果没有左兄弟，则与父节点、右兄弟进行三方合并

• 如果父节点是根节点

  • 并且三方合并后，父节点没有关键字了，那么将合并后得到的节点设置为根节点（树的高度将降低 1）， 然后退出
  • 否则直接退出，因为根节点没最少关键字个数的限制

• 否则令 node 等于其父节点，然后回到步骤 5

Python 实现

tim-chow 的 Github