11.3.B-树的不变量
\(11.3\)\(B\)-树的不变量
1.\(B\)-树的性质
由于\(B\)-树会在叶子容量过大时将叶子对半分开、然后重构子树,这使得我们可以以任意次序插入元素,而不用担心最坏运行时间的发生。
一棵\(B\)-树具有如下有用的性质:
- 每个叶子到它的源头(\(source\))的距离必须相等。
- 一个有\(k\)个元素的非叶子节点,它必须有\(k+1\)个孩子。
2.\(B\)-树运行时间分析
\(B\)-树的最坏运行情况是:在树的底部的叶子的最右侧的节点找到某个元素。由于\(B\)-树的构造方式,树的深度\(O(\log n)\),而由于我们限制了每个叶子结点承载元素的数量,因此从叶子左端到右端的搜索时间为常数。则总的运行时间为\(O(\log n)\)。