计算机知识B树及其基本操作思维导图

树中每个结点至多有m棵子树、至多有m-1个关键字

若根结点不是终端结点，则至少有两棵子树

除了根结点外的所有非叶结点至少有[m/2]↓棵子树

结点n的关键字个数：[m/2]↓-1<= n <= m-1

所有叶子结点都在同一层次上

所有结点的平衡因子都为0

B树中的大部分操作所需的磁盘存取次数与B树的高度成正比

n>=1,对任意一棵包含n个关键字，高度为h，阶数为m的B树，有如下性质：

关键字的个数满足：n <= m^h - 1

树的高度满足：h>=logm（n+1）

若让每个结点关键字最少，则容纳同样关键字的树的高度达到最大，高度范围太复杂。看书……

查找

插入

删除