\(11.3\)\(B\)-树的不变量

1.\(B\)-树的性质

  由于\(B\)-树会在叶子容量过大时将叶子对半分开、然后重构子树，这使得我们可以以任意次序插入元素，而不用担心最坏运行时间的发生。

  一棵\(B\)-树具有如下有用的性质：

• 每个叶子到它的源头(\(source\))的距离必须相等。
• 一个有\(k\)个元素的非叶子节点，它必须有\(k+1\)个孩子。

2.\(B\)-树运行时间分析

  \(B\)-树的最坏运行情况是：在树的底部的叶子的最右侧的节点找到某个元素。由于\(B\)-树的构造方式，树的深度\(O(\log n)\)，而由于我们限制了每个叶子结点承载元素的数量，因此从叶子左端到右端的搜索时间为常数。则总的运行时间为\(O(\log n)\)。