11.3.B-树的不变量

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

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

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

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

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

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

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