二叉树、平衡二叉树AVL、红黑树、B树、B+树

image.png

B树的阶数等于叶节点最大关键字数量+1（因为关键字两边都有指向子节点的指针-分叉）

在m阶(m叉)B树中除根结点外，任何节点至少[m/2]个分叉，即至少[m/2]-1个关键字，

[ ]代表向上取整。

节点内的关键字采用顺序查找或二分查找。

因为关键字太少会导致树变高，降低查找效率。另外就是保证同级子树的高度相同-平衡。

image.png

B+树的阶数与叶节点最大关键字数量相同，有与分块查找相似的地方；

分支节点中只包含它的叶子结点所有关键字中的最大值。

查找失败：关键字的记录(信息)为空，指向null

文章知识点与官方知识档案匹配，可进一步学习相关知识