一文搞懂二叉搜索树、B树、B+树、AVL树、红黑树( 二 ) _搜索树

文章插图
特点

所有叶子节点连接成为一个单链表，且这个链表是有序的。
所有关键字都在叶子节点出现，因此不可能在非叶子节点命中。
内节点不存数据，只存key 。
非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储数据的数据层。

B+Tree与B-Tree 的区别1）B树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B+树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。
2）在B树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B+树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。
思考：为什么说B+tree比B-tree更适合实际应用中操作系统的文件索引和数据库索引？
1) B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2) B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3)范围查找更快
MySQL是关系型数据库，经常会按照区间来访问某个索引列，B+树的叶子节点间按顺序建立了链指针，加强了区间访问性，所以B+树对索引列上的区间范围查询很友好。而B树的数据有一部分存在在非叶子节点上面，而且默认的B树的相邻的叶子节点之间是没有指针的，所以范围查找相对更慢。

AVL树（平衡二叉树）概念AVL、红黑树是对二叉搜索树的改进版本。
平衡因子：某个节点的左右子树深度之差。在一棵平衡二叉树中，节点的平衡因子只能取 0 、1 或者 -1，分别对应着左右子树等高，左子树比较高，右子树比较高。
AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。
不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

文章插图
如上图所示：任意节点的左右子树的平衡因子差值都不会大于1
AVL保持平衡的四种操作增删改查操作和二分搜索树类似，但是要多考虑的就是对节点的平衡考虑，如果一串数字的插入顺序为3，4，5 。那么这棵树结构就会退化为一个链表。而这时候AVL就会对这个树进行旋转操作来达到平衡，所以，我们就知道旋转的操作会在增加，删除，修改这三个地方进行旋转。旋转操作分为下面四种情况
1 LL右单旋转