平衡树
常见平衡树：平衡二叉查找树，2-3查找树，AVL树， 红黑树
2-3查找树
概述:保证查找树的平衡性，我们需要一些灵活性，允许树中的一个结点保存多个键。如
image.png
定义
2-3查找树要么为空，要么满足满足下面两个要求：
2-结点：
含有一个键(及其对应的值)和两条链，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大
于该结点。
3-结点：
含有两个键(及其对应的值)和三条链，左链接指向的2-3树中的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
查找
要判断一个键是否在树中，我们先将它和根结点中的键比较。如果它和其中任意一个相等，查找命中；否则我们就根据比较的结果找到指向相应区间的连接，并在其指向的子树中递归地继续查找。如果这个是空链接，查找未命中。
插入
2-3树需要做一些局部的变换来保持2-3树的平衡。
1.任意空链接到根结点的路径长度都是相等的。
2.4-结点变换为3-结点时，树的高度不会发生变化，只有当根结点是临时的4-结点，分解根结点时，树高+1
3.2-3树与普通二叉查找树最大的区别在于:
普通的二叉查找树是自顶向下生长，而2-3树是自底向上生长。
总结
直接实现2-3树比较复杂，在某些情况插入后的平衡操作可能会使得效率降低。因为：
1.需要处理不同的结点类型，非常繁琐；
2.需要多次比较操作来将结点下移；
3.需要上移来拆分4-结点；
4.拆分4-结点的情况有很多种；
红黑树
红黑树主要是对2-3树进行编码，红黑树背后的基本思想是用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示2-3树。我们将树中的链接分为两种类型：
红链接：将两个2-结点连接起来构成一个3-结点；
黑链接：则是2-3树中的普通链接。
我们将3-结点表示为由由一条左斜的红色链接(两个2-结点其中之一是另一个的左子结点)相连的两个2-结点。这种表示法的一个优点是，我们无需修改就可以直接使用标准的二叉查找树的get方法。
定义
红黑树是含有红黑链接并满足下列条件的二叉查找树:
- 红链接均为左链接；
- 没有任何一个结点同时和两条红链接相连；
- 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同；
平衡化
在对红黑树进行一些增删改查的操作后，很有可能会出现红色的右链接或者两条连续红色的链接，而这些都不满足红黑树的定义，所以我们需要对这些情况通过旋转进行修复，让红黑树保持平衡。
左旋：当某个结点的左子结点为黑色，右子结点为红色，此时需要左旋。
右旋：当某个结点的左子结点是红色，且左子结点的左子结点也是红色，需要右旋
红黑树根结点的颜色总是黑色
B树/B-树
B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在选择一个参数M，来构造一个B树，可以把它称作是M阶的B树，那么该树会具有如下特点：
1.每个结点最多有M-1个key，并且以升序排列；
2.每个结点最多能有M个子结点；
3.根结点至少有两个子结点；
实际应用中B树的阶数一般都比较大（通常大于100），所以，即使存储大量的数据，B树的高度仍然比较小，这样在某些应用场景下，就可以体现出它的优势
image.png
应用
在我们的程序中，不可避免的需要通过IO操作文件，而文件是存储在磁盘上的。计算机操作磁盘上的文件是通过文件系统进行操作的，在文件系统中就使用到了B树这种数据结构。
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。 为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。
文件系统的设计者利用了磁盘预读原理，将一个结点的大小设为等于一个页（1024个字节或其整数倍），这样每个结点只需要一次I/O就可以完全载入。
那么3层的B树可以容纳102410241024差不多10亿个数据，如果换成二叉查找树，则需要30层！
假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在10亿个数据中查找目标值，只需要小于3次硬盘读取就可以找到目标值，但红黑树需要小于30次，因此B树大大提高了IO的操作效率。
B+树
B+树是对B树的一种变形树，它与B树的差异在于:
- 非叶结点仅具有索引作用，也就是说，非叶子结点只存储key，不存储value；
- 树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据。
image.png
B+和B-树对比:
B+ 树的优点在于：
1.由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。
2.B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。
B树的优点在于：
由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value。
应用
在数据库的操作中，查询操作可以说是最频繁的一种操作，因此在设计数据库时，必须要考虑到查询的效率问题，区间查询
在很多数据库中，都是用到了B+树来提高查询的效率；
在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这个索引就是B+树这种数据结构实现的。
网友评论