KT

B Tree

DSA
最后修改于

B 树是 CS 中一种自平衡的树形数据结构，可以保证数据的有序性。
得益于其有序的树形结构，其查找性能相比线性结构更优秀。

特性#

  • 具有良好的查找，插入，删除性能，均为 O(logn)O(logn)
  • 可用于数据库索引，和文件系统

基本结构#

对于每个非叶节点而言，可以有一定数量范围的子节点。
因此相比于其他自平衡二叉树而言，在保持平衡上花费的时间相对而言会少一些，相应的代价是花费的空间会更多。
对于一般的树形结构，其结构通常为左边的样式。
loading...
B Tree 对节点内部的结构进行了定义。

  1. 每个节点包含若干个内部节点（aka key node），包含 n + 1 个指向其他子节点的指针。
  2. 如果我们定义 func anyV(poninter) = any value in pointer or pointer's children。那么节点内部有这样的比较关系anyV(pa)≤va≤anyV(pb)≤vb≤anyV(pc)anyV(pa) \le va \le anyV(pb) \le vb \le anyV(pc)
    通过进行以上操作，我们成功定义出了一个有序的多叉树，可以满足查找的需求。
    但是与其他平衡树类似，当向树内插入 / 删除节点的时候，需要保持树的平衡。
class BTree<T: Comparable<T>>(
	t: Int
	var root: BTreeNode<T>
)

data class BTreeNode<T: Comparable<T>>(
	var leaf:Boolean
	val keys: MutableList<T>
	val children: MutableList<BTreeNode<T>>
)

插入操作#

插入的时候，以优先向叶子结点插入，当叶子结点没有空余空间时，拆分父节点为原则进行插入。这可以保证树的高度是平衡的，从下面的步骤可以看出。
比如在这样的树中，插入一个名为 90 的节点。
loading...
如上，当需要插入的时候，从根节点比较，直到选到合适的叶子节点位置。
但是当叶子空间不足的时候，就需要拆分。
loading...
拆分后，将中间节点提取，插入到父亲节点中，即使父亲节点满了，可以用同样的步骤拆分父亲节点，往更上一级进行插入，这可以保证，叶子节点的深度是一样的，也就是平衡的，证明此处从略。（这种方式就是所谓的向上生长）。

因此再来看几条没有被提到的性质。

  1. B 树有一个 t 属性，每个非根节点且非叶节点至少有 t 个子节点，最多包含 2t 个子节点， 叶节点有t~t-1个内部节点。
  2. 在根节点不为叶子节点的情况下，至少具有一个内部节点。
    这两条性质即是按上述向叶子结点插入，当叶子结点没有空余空间时，拆分父节点的插入原则的表现。
    值得注意的是，在另外一种定义中。通过定义最大度degree来确定每个节点的子节点数目范围，每个非根节点且非叶节点最多有 m 个子节点，最少有 ⌈m/2⌉ 个子节点。

从上面不难看出，主要有两个操作，插入数据和拆分节点。但如何判断何时需要拆分节点？拆分节点是否会影响到树高？
对于第一个问题，在扫描当前节点并找到了插入的位置，需要提前判断对应位置的子节点是否满。
如果当前的节点不是满的，即是子树需要拆分，也可以将拆分到范围限制到当前节点对应的子树，不会进一步向上传播。
loading...
因此 insert 操作可以拆分为：

  1. 扫描 root 节点, 如果 root 节点满，拆分 root 节点
  2. root 节点非满，对其执行insertNotFull(node, v)。
    insertNotFull 步骤如下：
  3. 如果是叶子节点，找到合适的位置插入
  4. 如果是非叶子节点，找到找到合适的子节点
  5. 如果子节点满，进行拆分子节点。
  6. 如果子节点不满，对其执行insertNotFull(node, v)。
    因此实现该操作只需要实现三个部分 insert、insertNotFull、splitChild

删除操作 ()#

删除叶节点

  1. 如果当前叶节点的内部节点数大于最小值，那么直接删除

  2. 如果当前叶节点的内部节点数等于最小值，那么找兄弟叶节点借用。如图，删除73，将父亲节点的55作为替换，再从左边兄弟节点借用53取代 55的位置。
    loading...

  3. 如果兄弟节点也为最小值，那么合并两个叶节点，可以保证新节点不超过特定值。
    loading...
    但是这有可能会让父亲节点违反 B 树的规则。所以这样以叶节点为基准的删除方式是不合适的。

因此，不妨切换思路，从root开始考虑删除。
对于一个给定的 t值，每个节点中，至少含有 t-1个内部节点（t个子节点），最多含有2t-1个内部节点 (2t个子节点)。

对于一颗子树，如果他有n(n>=t) 个内部节点，我们企图从这个子树上删除一个元素。
那么该删除操作一定可以在其内部完成，并且高度不变，且不波及其父亲节点。

对于一颗子树，如果它只有n个内部节点，且n = (t-1)，在这种情况下，存在一种极端情况，子树中的任何节点中，都只有 t-1个内部节点，删除任何节点都会导致子树不再满足 B 树的限制，因此必须在进入该节点前，就由其父亲节点协调。
具体分为两种情况：

  1. 左右兄弟节点的内部节点数至少有一个大于最小值
    loading...
    如图，在遍历parent节点的时候，通过比较可以要删除的值是在 以 M为根的子树上，但是 M的内部节点只有 2个，因此可能会是边界情况。
    因此 P 此时先尝试向L 或 R 子树借取一个内部节点。
    在上图中，因为L的内部节点大于最小值，因此可以从 L 中取出最大值max(L)，并将其从 L 中删除，这可以保证 L 只需要在内部调整即可以保证正确删除。
    随后用max(L)取代53，并将 53 放入 mid 子树中。再以M为子树删除 v。

  2. 左右兄弟节点的内部节点数均为最小值
    loading...
    如图，在遍历parent节点的时候，通过比较可以要删除的值是在 以 M为根的子树上，但是 M的内部节点只有 2个，因此可能会是边界情况。此时 L,R 的内部节点均为最小值，因此 P 此时需要协调，将 M 与L 或 R 进行合并。此时再以left(L) + mid(M)合并后的子树为根，删除v


fun delete(node, value) {
	// a index that node.internalValue[i] >= value
	var index = findProperIndex(node)
	if(node.isNotLeaf() && node.values[index] != value) {
		//maybe node.children[index] is rightChild, but we ignore here
		val lc = node.children[index]
		val rc = node.children[index+1]
		// both left child and right child has minial internal nodes
		if(!lc.moreThanMinInteralNodes() && !rc.moreThanMinInteralNodes()){
			merge(node, index, index+1)
		}else if(lc.moreThanMinInteralNodes()) {
			borrowFromLeft(node)
		}else {
			borrowFromRight(node)
		}
		// remove from value from subtree
		delete(node.chidren[index], value)
	} else if(node.internalValue[i] == value) {
		deleteInternalNode(node, value, index)
	}else {
		// due to merge ops, code here can promiase that
		// leaf size is more than minial internal node size
		// so just delete it is ok.
		deleteFromLeaf(node,v)
	}
}

其他实现#

在有的实现中， B TreeNode 保留了 Root 节点以及父亲节点的指针，这样做可以先执行删除操作，随后再进行修复。
另外，数据库索引的实现中通常还为其增加并发特性，使得该数据结构线程安全。
在 Linux 内核中，其变体为 Maple 树，可以减少虚拟内存管理中的锁争用。