这部分内容较少,B树要理解基本特性,掌握其建立、插入和删除操作;B+树只需要掌握基本概念即可
1.B树及其基本操作
b树是在平衡二叉树的基础上的衍生概念
(1)B树的定义:m阶B树即为所有结点的平衡因子均等于0的m路平衡查找树
复习:m叉树指的是结点的最大子树数目,而不是说m叉树的每个非叶结点都必须是m叉的
解释:
1.这里先记住B树每个结点最多有m棵子树即可,关于每个结点的关键字个数问题在下面会解释
2.这里说的比较含混(这书写的什么b玩意),根节点不是叶结点指的是根节点中有关键字,即这条定义可以描述为下面这样:
如果根节点没有关键字,则这个根节点下面不会有子树,整个B树为空;如果根节点中有关键字,则其子树个数必然≥2。(这里是因为子树个数等于结点关键字个数+1)
3.