阿狗工具
二叉树、平衡二叉树AVL、红黑树、B树、B+树
2024-04-10 05:00:54 阅读数 932
image.png
B树的阶数等于叶节点最大关键字数量+1（因为关键字两边都有指向子节点的指针-分叉）
在m阶(m叉)B树中除根结点外，任何节点至少[m/2]个分叉，即至少[m/2]-1个关键字，
[ ]代表向上取整。
节点内的关键字采用顺序查找或二分查找。
因为关键字太少会导致树变高，降低查找效率。另外就是保证同级子树的高度相同-平衡。
image.png
B+树的阶数与叶节点最大关键字数量相同，有与分块查找相似的地方；
分支节点中只包含它的叶子结点所有关键字中的最大值。
查找失败：关键字的记录(信息)为空，指向null
文章知识点与官方知识档案匹配，可进一步学习相关知识