学习红黑树之前先理解一下二叉查找树(BST),二叉查找树的特性:
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
如图,一个普普通通的二叉树:
查找某个节点所需的最大次数等同于BST的高度,插入节点时也是利用类似的方法一层层比较大小查找到新节点合适的插入位置.这么来看虽然二叉树确实是一个强大的数据结构,但某些情况下也会暴露出它的缺陷.
缺陷暴露在新节点插入的时候,我们来看看以下例子:
(1)假设初始的二叉查找树只有三个节点，根节点值为9，左孩子值为8，右孩子值为12：
(2)接下来我们依次插入如下五个节点：7,6,5,4,3。呃…由下图可见,它成了长短腿.如果我们查的是3,那么查找次数就是数的高度
二叉查找树性能总结:这样的形态确实也符合二叉查找树的特性,可是查找的性能大打折扣.由此可见,二叉查找树如果在分布比较对称均匀的情况下,每次比较都会把范围缩短一半,其时间复杂度为O(log2(n)),在最坏的情况下,即BST只有左子树或右子树的情况下,其时间复杂度是O(n).因此BST的效率和它的形态有密切的关系,一颗形态分布均匀的BST才能发挥其最高效率,所以要发挥其最高效率就要将它的形态"平衡",就有了平衡二叉树.
红黑树,一种特殊的平衡二叉树红黑树(Red&Black Tree)除了符合BST的特性外,其的节点会分出一个存储位来标记其颜色(标颜色是为了更好地通过颜色相关的规则来检验树的平衡性),比BST多出如下的附加特性:
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
如图,一棵有颜值的红黑树:
正因为这些规则的限制,保证了RBT的形态自平衡,RBT从根节点到叶子的最长路径不会超过最短路径的2倍.
当对RBT进行节点插入删除操作的时候可能会破坏红黑树的规则,这时红黑树就要通过一些操作达到形态平衡的目的.
RBT自平衡的三种操作左旋、右旋和变色。
左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。如图:
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。如图:
先忽略颜色，可以看到旋转操作不会影响旋转结点的父结点，父结点以上的结构还是保持不变的,所以旋转操作是局部的。那变色又是一种什么样的操作呢?
变色：结点的颜色由红变黑或由黑变红。
下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4(不能连续2个红)，所以把节点22从红色变成黑色：
但这样并不算完，因为凭空多出的黑色节点打破了规则5(节点到其每个叶子的所有路径都包含相同数目的黑色节点)，所以发生连锁反应，需要继续把节点25从黑色变成红色：
当然,RBT的节点插入和删除情况复杂,具体情况具体分析,下边举一个典型的例子让大家体会一下:
以刚才的红黑树插入21为例:
首先，可以看到出现两个红,我们需要做的是变色，把节点25及其下方的节点变色：
此时又出现连续的两个红色节点，那么把节点17变成黑色节点？恐怕不合适。这样一来不但打破了规则5(从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点)，而且根据规则2（根节点是黑色），也不可能把节点13变成红色节点。
变色已无法解决问题,那么我们就考虑旋转.这里就用上了左旋.以13为支点,将右子树的左上挪动,即将17挪动到13的位置,13挪动到左下的位置,17原来的左子树,接到13,成为13的右子树:
旋转后:
我擦!!怎么又有两个连红,没事,我们继续变色:
完事了麽?走一下路径看看符不符合规则5(从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点).其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4，其他路径的黑色节点个数是3，不符合规则5。没事,再旋转一次!
以13当作支点进行右旋:
8上13下,11接到13:
又有连红!!好吧,这回应该根据规则变色:
我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂，经历了如下步骤：
变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色
JDK集合类中的TreeMap和TreeSet, Java8中的HashMap…
红黑树为什么他配不上MySql索引你确定应用到数据库索引,它的性能好麽?
其实从算法逻辑来讲,二叉树的查找速度和比较次数都是最小的,但是数据文件存储的位置是再磁盘,这不得不考虑一个现实的问题,磁盘IO(磁盘IO的存取次数就是评价一个数据库索引优劣的关键性指标), 利用索引查询数据的时候,逐一加载磁盘页到内存当中,每一页对应索引树的节点.如果拿红黑树作为索引会出现什么情况呢?
查询数据的时候每比较一遍,都会进行一次磁盘IO,在最坏的情况下比较的次数就是树的高度,而且节点能存放的数据又少得可怜,所以又高又瘦的红黑树并不适合作为索引.索引需要的是减少磁盘IO的次数以及节点存储更多的数据量.
磁盘页:这一概念有计算机基础的同学应该都理解,简单来说,操作系统经常与内存和硬盘这两种存储设备进行通信，与内存操作，是虚拟一个页的概念来作为最小单位。 举个不是很恰当的例子:硬盘是锅,数据是饭,内存是碗,而页就是饭勺.
B树 什么是B树 B树(Balance Tree)是一种多路平衡查找树(多路:每个节点的子节点可以多于两个),一个m阶的B树具有如下几个特征(阶:树中所有孩子结点个数的最大值称为该树的阶)：
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
如图,一颗又矮又有内涵的3阶B树:
我们对照以上特性分析一下这棵树:
(2,6)节点中有2,6 两个元素, 又有三个孩子1, (3,5), 8 (符合特性2:每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m 以及特性3:每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m,在本例中1<=k<=3)
1小于2在(2,6)左边, (3,5)在[2,6]之间,放中间. 8大于6放右边(符合特性5:每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。)
再看看根节点和叶子节点,分别符合特性1,特性4.这就是一颗B树.
B树的查询性能分析 在上边的树中查询5
(1)第一次磁盘IO
(2)节点加载到内存,在内存中定位(和9进行比较)
(3)第2次磁盘IO：
(4)节点加载到内存,在内存中定位（和2，6比较）：
(5)第3次磁盘IO：
(6)节点加载到内存,在内存中定位(和3，5比较),终于找到了：
通过整个流程我们可以看出,B树的查询比较次数并不比二叉树少,尤其是节点元素的个数很多的时候.但是相比较于磁盘IO的速度,内存中比较耗时可以忽略不计,每个节点找到后会加载到内存当中,因此在同一节点查找数据的时间可以忽略不记,节点元素多个个数正好成为了B树的优势.
所以只要树足够低,IO次数足够少,就可以提升查找性能.
B树的增删 B树的插入新节点的情况分为多种情况,且比较复杂,这里只举一个典型的例子:
在上边B树的基础上添加4:
自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。
根据规则2和3,节点不能超过两个,节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是根据值域划分的规则拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。
虽然插入节点可能引发的连锁反应比较大,但也正是如此B树能始终维持多路平衡
接下来,举一个删除的例子,删除元素11:
自顶向下查找元素11的节点位置
删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）
最终得到以下的形态
B树的应用
主要应用于文件系统以及部分数据库索引,比如著名的非关系型数据库MongoDB.而大部分的关系型数据库如我们的MySql则是使用B+树作为索引.
B树和B+树差在哪里呢?
B+树 什么是B+树B+树(B+ Tree)是B树的plus版本,在数据库应用中有着比B树更高的查询性能,他俩有许多共同点,但是B+树在B树基础上具备一些新的特征,一个m阶的B+树具有如下几个特征：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
这是一颗有内涵有家底的3阶B+树:
对比特性,我们分析一下这颗B+树:
根节点的8是(2,5,8),(6,8)的最大元素, 根节点的15是(11,15),(13,15)的最大元素.符合规则3(所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。本例是最大的情况).
同时,所有叶子节点都包含了父节点的所有元素,符合规则2.
(2,5,8)的度是3,有3个孩子,(11,15)节点有两个元素又有两个孩子,符合规则1.
值得注意的是:根节点的最大元素就是B+树的最大元素,以后无论插入删除多少元素都要保证最大的元素在根节点当中. 叶子不仅包含了B+树的全量元素信息,并且每个叶子都带有指向下一个节点的指针,形成一个有序链表:
B+树还具有一个特点,那就是卫星数据的位置处于最下层,那什么是卫星数据呢?
卫星数据:索引元素所指向的数据记录,比如说数据库的某一行,在B树中,无论中间节点还是叶子节点都带有卫星数据.
B-树中的卫星数据（Satellite Information）：
而在B+树中只有叶子节点带有卫星数据,其余节点仅仅是索引而没有数据关联.
B+树中的卫星数据（Satellite Information）：
在节点占用空间恒定的情况下，B+树的度更大,单个节点的元素更多。比如同样节点大小，B树的每个节点有100个元素+卫星数据，B+树的每个节点就可以装下1000个元素,数据存于最下层。这样的好处就是树的高度降低同时让节点有更多的元素。(度:每个节点的存储元素个数)
B+树查询性能分析那B+树设计成这样相较于B树又有那些优势呢?当然是查询性能.拿范围查询做对比会更加明显,这里举一个例子:
查询3到11的元素
B树的范围查询过程:
(1)自顶向下，查找到范围的下限（3）：
(2)中序遍历到元素6：
(3)中序遍历到元素8：
(4)中序遍历到元素9：
(5)中序遍历到元素11，遍历结束：
相较于B树的范围查找,B+树要简洁的多,同样是查询3到11的元素,B+树查找如下:
(1)自顶向下，查找到范围的下限（3）：
(2)通过链表指针，遍历到元素6, 8：
(3)通过链表指针，遍历到元素9, 11，遍历结束：
综合来看,B+树相较于B树的优势有三个:
1.单一节点存储更多的元素，更少的IO次数
2.所有查询都要查找到叶子节点,查询性能更稳定
3.所有叶子节点形成有序链表,范围查询更简单
至于删除和添加节点,和B树差不多,在此不做赘述.
补充 如果查询的节点不在根结点，那就很难保证io次数谁多谁少，只不过范围查找的确b+更 稳定
ps:大部分图文来源于微信公众号:程序员hhdhm
在线生成树:
二分查找树:https://www.cs.usfca.edu/~galles/visualization/BST.html
红黑树:https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
B树:https://www.cs.usfca.edu/~galles/visualization/BTree.html