AVL树、B树、B+树（1-基本概念）

喜欢ヅ旅行 2021-09-26 14:42 315阅读 0赞

AVL树（平衡二叉树）  
定义：  
（1） 左子树与右子树的高度差只能是-1，0，1。  
（2） 树中的每个左子树和右子树都是AVL树

B树（多路平衡查找树）：  
B树中所有结点的孩子结点数的最大值称为B树的阶，通常用m表示。一棵m阶B树或者空树，或为满足如下特征的m叉树：  
（1） 树中每个结点至多有m棵子树（即至多含有m-1个关键字）  
（2） 若根结点不是终端结点，则至少有两棵子树  
（3） 若根节点外的所有非叶结点至少有（m/2）（向上取整）棵子树，即至少含有（m/2-1）个关键字  
（4） 所有非叶节点的结构如下：  
![这里写图片描述][70]

Ki(i1,2,…n)为结点的关键字，且满足K1到Kn递增。Pi（i=0,1,…n）为指向子树根节点的指针，且指针Pi-1所指子树所有结点的关键字均小于Ki,Pi所指子树中所有结点的关键字均大于Ki。n为结点中关键字的个数。  
（5） 所有叶结点都出现在同一层次上，并且不带信息（可以看做是外部结点或者类似于折半查找判定树的查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）  
B树是所有结点的平衡因子均等于0 的多路查找树，如下图所示（一棵3阶B树）：  
![这里写图片描述][70 1]

B+树（应数据库所需而出现的一种B树的变形树）：  
一棵m阶的B+树需满足以下条件：  
（1） 每个分支结点最多有m棵子树（结点）  
（2） 非叶根结点至少有两颗子树，其他分支结点至少有（m/2）棵子树  
（3） 结点的子树个数与关键字个数相等  
（4） 所有叶结点包含全部关键字及指向相应记录的指针，而且叶结点中将关键字按大小顺序排列，并且相邻叶结点按照大小顺序相互链接起来。  
（5） 所有分支结点（可看成是索引的索引）中仅包含它的各个子节点（即下一级的索引快）中关键字的最大值及指向其子结点的指针。  
m阶B+树VSm阶B树  
（1） 在B+树中，具有n个关键字的结点只包含n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有（n+1）棵子树  
（2） 在B+树中，每个结点（非根结点）关键字个数n的范围是（m/2）<=n<=m(根结点：1<=n<=m)，在B树中，每个结点（非根结点）关键字个数n的范围是（m/2）-1<=n<=m-1(根结点1<=n<=m-1)。  
（3） 在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址  
（4） 在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中，而在B树中，叶结点包含的关键字和其他节点包含的关键字是不重复的。  
下图为一棵4阶B+树的示例：  
![这里写图片描述][70 2]

[70]: /images/20210923/8f8d11e12c4c4a6aae94cce9e1048d29.png
[70 1]: /images/20210923/692069b327024452bdb6f51b021fe7d8.png
[70 2]: /images/20210923/cf19a4869cd044ca961b39eda81cd58d.png