共计 7509 个字符，预计需要花费 19 分钟才能阅读完成。
数据库经常存放了大量的数据，数据库的查询也是经常发生的。
当我们要查询一个庞大的数据表中的一行小小的数据的时候，就像茫茫人海中找到一个对的人一样困难 …
我们为了节约时间成本，我们一定要想办法以最快的速度找到我们想要的数据。
学过数据结构的童鞋一定第一个想到：搜索树，其平均复杂度是 log(n)，具有不错的查询性能。
好的，故事从一个简单的二叉树开始 ……
1、二叉查找树
（1）二叉树简介：
二叉查找树也称为有序二叉查找树，满足二叉查找树的一般性质，是指一棵空树具有如下性质：
1、任意节点左子树不为空, 则左子树的值均小于根节点的值；
2、任意节点右子树不为空, 则右子树的值均大于于根节点的值；
3、任意节点的左右子树也分别是二叉查找树；
4、没有键值相等的节点；
上图为一个普通的二叉查找树，按照中序遍历的方式可以从小到大的顺序排序输出：2、3、5、6、7、8。二叉树的查找平均时间复杂度是 O(log(n))。
大家看上图，如果我们的根节点选择是最小或者最大的数，那么二叉查找树就完全退化成了线性结构。
虽然我们已经拥有了平均 O(log(n))的时间复杂度，但是，人类是贪心的。我们接受不了在极端情况下时间复杂度退化成 O(n)。
思来想去，极端情况下这棵树已经失去了平衡，如果我们让他恢复平衡，岂不是很美妙。那就给他取个名字叫：平衡二叉树。
2、红黑树
红黑树就是平衡二叉树的一种。
红黑树在每个节点增加一个存储位表示节点的颜色，可以是 red 或 black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。
红黑树的性质：
1、每个节点非红即黑；
2、根节点是黑的；
3、每个叶节点 (叶节点即树尾端 NULL 指针或 NULL 节点) 都是黑的；
4、如果一个节点是红的, 那么它的两儿子都是黑的；
5、对于任意节点而言，其到叶子点树 NULL 指针的每条路径都包含相同数目的黑节点；
6、每条路径都包含相同的黑节点；
注意：
性质 3 中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java 实现的红黑树将使用 null 来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。
性质 4 的意思是：从每个根到节点的路径上不会有两个连续的红色节点，但黑色节点是可以连续的。
因此若给定黑色节点的个数 N，最短路径的情况是连续的 N 个黑色，树的高度为 N – 1; 最长路径的情况为节点红黑相间，树的高度为 2(N – 1)。
性质 5 是成为红黑树最主要的条件，后序的插入、删除操作都是为了遵守这个规定。
（1）红黑树的左旋右旋
红黑树的左右旋是比较重要的操作，左右旋的目的是调整红黑节点结构，转移黑色节点位置，使其在进行插入、删除后仍能保持红黑树的 5 条性质。
左旋
// 左旋代码
__leftRotate(x) {
// x 是要将要旋转到左子树的节点
if (x != null) {
// y 是将要旋转到父节点位置的节点
var y = x.right;
// 把 y 的左节点移到 x 的右节点 把 x 的右儿子改为 y 的左儿子
x.right = y.left;
if (y.left != null) {
// 因为要移动了 y 的左节点 它成为了 x 的儿子 所以要把 y.left 的爸爸改为 x
y.left.parent = x;
}
// x 的爸爸变成了 y 的爸爸
y.parent = x.parent;
if (x.parent == null) {
// 如果 x 是根节点了 那么记得把 root 换成 y
this.root = y;
}
else if (x.parent.left == x) {
// 如果 x 自身原本是 左儿子 则把 x 的父亲的左儿子 换成 y
x.parent.left = y;
}
else {
// 如果 x 自身原本是 右儿子 则把 p 的父亲的右儿子 换成 y
x.parent.right = y;
}
// 把 x 变成 y 的左儿子
y.left = x;
// 把 x 的 父亲变成 y
x.parent = y;
}
}右旋
// 右旋代码
__rightRotate(p) {if (p != null) {
var l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}（2）红黑树的平衡插入
红黑树的插入主要分两步：
1、首先和二叉查找树的插入一样，查找、插入
2、然后调整结构，保证满足红黑树状态
对结点进行重新着色
以及对树进行相关的旋转操作
红黑树的插入在二叉查找树插入的基础上，为了重新恢复平衡，继续做了插入修复操作。
第一步：
二叉查找树的就是一个二分查找，找到合适的位置就放进去。
__insert(node) {
var y = null;
var x = this.root;
// 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。while (x != null) {
y = x;
if(node.key < x.key) {x = x.left;}
else {x = x.right;}
}
// 找到 node 将要插入的位置 y
node.parent = y;
if (y!=null) {if (node.key < y.key) {y.left = node;}
else {y.right = node;}
} else {
// 空树
this.root = node;
}
// 设置节点的颜色为红色
node.color = 'RED';
// 将它重新修正 使其符合红黑树
this.insertFixUp(node);
}第二步：插入后调整红黑树结构
红黑树的第 5 条特征规定，任一节点到它子树的每个叶子节点的路径中都包含同样数量的黑节点。也就是说当我们往红黑树中插入一个黑色节点时，会违背这条特征。
同时第 4 条特征规定红色节点的左右孩子一定都是黑色节点，当我们给一个红色节点下插入一个红色节点时，会违背这条特征。
前面说了，插入一个节点后要担心违反特征 4 和 5，数学里最常用的一个解题技巧就是把多个未知数化解成一个未知数。我们这里采用同样的技巧，把插入的节点直接染成红色，这样就不会影响特征 5，只要专心调整满足特征 4 就好了。这样比同时满足 4、5 要简单一些。
染成红色后，我们只要关心父节点是否为红，如果是黑的，直接插入，无需调整。如果是红的，就要把父节点进行变化，让父节点变成黑色，或者换一个黑色节点当父亲，这些操作的同时不能影响 不同路径上的黑色节点数一致的规则。
注：插入后我们主要关注插入节点的父亲节点的位置，而父亲节点位于左子树或者右子树的操作是相对称的，这里我们只介绍一种，即插入位置的父亲节点为左子树。
插入、染红后的调整有 2 种情况：
情况 1. 父亲节点和叔叔节点都是红色：
假设插入的是节点 N，这时父亲节点 P 和叔叔节点 U 都是红色，爷爷节点 G 一定是黑色。
红色节点的孩子不能是红色，这时不管 N 是 P 的左孩子还是右孩子，只要同时把 P 和 U 染成黑色，G 染成红色即可。这样这个子树左右两边黑色个数一致，也满足特征 4。
但是这样改变后 G 染成红色，G 的父亲如果是红色岂不是又违反特征 4 了？
这个问题和我们插入、染红后一致，因此需要以 爷爷节点 G 为新的调整节点，再次进行调整操作，以此循环，直到父亲节点不是红的，就没有问题了。
情况 2. 父亲节点为红色，叔叔节点为黑色：
假设插入的是节点 N，这时父亲节点 P 是红色，叔叔节点 U 是黑色，爷爷节点 G 一定是黑色。
红色节点的孩子不能是红色，但是直接把父亲节点 P 涂成黑色也不行，这条路径多了个黑色节点。怎么办呢？
既然改变不了你，那我们就此别过吧，我换一个更适合我的！
我们怎么把 P 弄走呢？看来看去，还是右旋最合适，通过把 爷爷节点 G 右旋，P 变成了这个子树的根节点，G 变成了 P 的右子树。
右旋后 G 跑到了右子树上，这时把 P 变成黑的，多了一个黑节点，再把 G 变成红的，就平衡了！
上面讲的是插入节点 N 在父亲节点 P 的左孩子位置，如果 N 是 P 的右孩子，就需要多进行一次左旋，把情况化解成上述情况。
N 位于 P 的右孩子位置，将 P 左旋，就化解成上述情况了。
下面是 RBTree 在插入后进行调整的代码:
/*
* 红黑树插入修正函数
*
* 在向红黑树中插入节点之后(失去平衡)，再调用该函数；* 目的是将它重新塑造成一颗红黑树。*
* 参数说明：* node 插入的结点
*/
insertFixUp(node) {
var parent, gparent;
// 若“父节点存在，并且父节点的颜色是红色”while (((parent = node.parent)!=null) && this.__isRed(parent)) {
gparent = parent.parent;
// 若“父节点”是“祖父节点的左孩子”if (parent == gparent.left) {
// Case 1 条件：叔叔节点是红色
var uncle = gparent.right;
if ((uncle!=null) && this.__isRed(uncle)) {this.__setBlack(uncle);
this.__setBlack(parent);
this.__setRed(gparent);
node = gparent;
continue;
}
// Case 2 条件：叔叔是黑色，且当前节点是右孩子
if (parent.right == node) {
var tmp;
this.__leftRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3 条件：叔叔是黑色，且当前节点是左孩子。this.__setBlack(parent);
this.__setRed(gparent);
this.__rightRotate(gparent);
} else { // 若“z 的父节点”是“z 的祖父节点的右孩子”// Case 1 条件：叔叔节点是红色
var uncle = gparent.left;
if ((uncle!=null) && this.__isRed(uncle)) {this.__setBlack(uncle);
this.__setBlack(parent);
this.__setRed(gparent);
node = gparent;
continue;
}
// Case 2 条件：叔叔是黑色，且当前节点是左孩子
if (parent.left == node) {
var tmp;
this.__rightRotate(parent);
tmp = parent;
parent = node;
node = tmp;
}
// Case 3 条件：叔叔是黑色，且当前节点是右孩子。this.__setBlack(parent);
this.__setRed(gparent);
this.__leftRotate(gparent);
}
}
// 将根节点设为黑色
this.__setBlack(this.root);
}OK, 到目前为止，我们已经构建好一个红黑树了。我们可以打印出来瞧瞧：
var rb_tree = new RBTree();
rb_tree.insert(1);
rb_tree.insert(2);
rb_tree.insert(3);
rb_tree.insert(4);
rb_tree.insert(5);
rb_tree.insert(6);
rb_tree.insert(7);
rb_tree.insert(8);
rb_tree.insert(9);
rb_tree.insert(10);
console.log(rb_tree.getRoot());
在线生成红黑树地址 https://sandbox.runjs.cn/show…
红黑树的应用：
1、广泛用于 C ++ 的 STL 中，Map 和 Set 都是用红黑树实现的；
2、著名的 Linux 进程调度 Completely Fair Scheduler，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点，左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间；
3、IO 多路复用 epoll 的实现采用红黑树组织管理 sockfd，以支持快速的增删改查；
4、Nginx 中用红黑树管理 timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器；
5、Java 中 TreeMap 的实现；
诶呀，费了一大把劲终于把红黑树讲完了。不过还是有收获滴~ 我们刚刚的操作提高了查找的性能。
对于数据库的查找问题，感觉看到了希望！不过，等等。。。
牵扯到一个问题了，不考虑每种数据结构的前提条件而选择数据结构都是在耍流氓。
红黑树基本都是存储在内存中才会使用的数据结构，那磁盘中会有什么不同呢？
这就要牵扯到磁盘的存储原理了
操作系统读写磁盘的基本单位是扇区，而文件系统的基本单位是簇(Cluster)。
也就是说，磁盘读写有一个最少内容的限制，即使我们只需要这个簇上的一个字节的内容，我们也要含着泪把一整个簇上的内容读完。
那么，现在问题就来了
一个父节点只有 2 个子节点，并不能填满一个簇上的所有内容啊？那多余的内容岂不是要浪费了？我们怎么才能把浪费的这部分内容利用起来呢？哈哈，答案就是 B/B+ 树。
由于 B/B+ 树分支比二叉树更多，所以相同数量的内容，B+ 树的深度更浅，深度代表什么？代表磁盘 io 次数啊！数据库设计的时候 B+ 树有多少个分支都是按照磁盘一个簇上最多能放多少节点设计的啊！
所以，涉及到磁盘上查询的数据结构，一般都用 B/B+ 树啦。
3、B/B+ 树
B/B+ 树是为了磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉，B 树每个内节点有多个分支)，与红黑树相比，在相同的的节点的情况下，一颗 B /B+ 树的高度远远小于红黑树的高度(在下面 B /B+ 树的性能分析中会提到)。B/B+ 树上操作的时间通常由存取磁盘的时间和 CPU 计算时间这两部分构成，而 CPU 的速度非常快，所以 B 树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下 B 树的高度越小，磁盘 I / O 所花的时间越少。
（1）B 树
B 树也称 B - 树, 它是一颗多路平衡查找树。我们描述一颗 B 树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母 m 表示阶数。当 m 取 2 时，就是我们常见的二叉搜索树。
一颗 m 阶的 B 树定义如下：
1）每个结点最多有 m - 1 个关键字。
2）根结点最少可以只有 1 个关键字。
3）非根结点至少有 Math.ceil(m/2)- 1 个关键字。
4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
上图是一颗阶数为 4 的 B 树。在实际应用中的 B 树的阶数 m 都非常大（通常大于 100），所以即使存储大量的数据，B 树的高度仍然比较小。每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子结点的指针。我们将一个 key 和其对应的 data 称为一个记录。但为了方便描述，除非特别说明，后续文中就用 key 来代替（key, value）键值对这个整体。在数据库中我们将 B 树（和 B + 树）作为索引结构，可以加快查询速速，此时 B 树中的 key 就表示键，而 data 表示了这个键对应的条目在硬盘上的逻辑地址。
B 树的插入操作:
插入操作是指插入一条记录，即（key, value）的键值对。如果 B 树中已存在需要插入的键值对，则用需要插入的 value 替换旧的 value。若 B 树不存在这个 key, 则一定是在叶子结点中进行插入操作。
1）根据要插入的 key 的值，找到叶子结点并插入。
2）判断当前结点 key 的个数是否小于等于 m -1，若满足则结束，否则进行第 3 步。
3）以结点中间的 key 为中心分裂成左右两部分，然后将这个中间的 key 插入到父结点中，这个 key 的左子树指向分裂后的左半部分，这个 key 的右子支指向分裂后的右半部分，然后将当前结点指向父结点，继续进行第 3 步。
下面以 5 阶 B 树为例，介绍 B 树的插入操作，在 5 阶 B 树中，结点最多有 4 个 key, 最少有 2 个 key
找到了一个非常适合数据库索引的数据结构，感觉自己棒棒哒~
但是，人类的贪心永无止境 …
我们想想，B 树的每个节点都有 data 域（指针），这无疑增大了节点大小，说白了增加了磁盘 IO 次数（磁盘 IO 一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO 次数增多，一次 IO 多耗时啊！），是不是我们可以除了叶子节点其它节点并不存储数据，节点小，磁盘 IO 次数就少。
如果所有的 Data 域在叶子节点，那我们将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。遍历效率突然一下提高了！而且在数据库中基于范围的查询是非常频繁的，而 B 树不支持这样的操作（或者说效率太低）
（2）B+ 树
各种资料上 B + 树的定义各有不同，一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式，即关键字个数比孩子结点个数小 1，这种方式是和 B 树基本等价的。上图就是一颗阶数为 4 的 B + 树。
除此之外 B + 树还有以下的要求。
1）B+ 树包含 2 种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有 1 个。
2）B+ 树与 B 树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
3）m 阶 B + 树表示了内部结点最多有 m - 1 个关键字（或者说内部结点最多有 m 个子树），阶数 m 同时限制了叶子结点最多存储 m - 1 个记录。
4）内部结点中的 key 都按照从小到大的顺序排列，对于内部结点中的一个 key，左树中的所有 key 都小于它，右子树中的 key 都大于等于它。叶子结点中的记录也按照 key 的大小排列。
5）每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。
B+ 树的插入：
B/B+ 树性能分析
B-Tree 中一次检索最多需要 h - 1 次 I /O（根节点常驻内存），渐进复杂度为 O（h）=O（logmN）。一般实际应用中，m 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3）。
综上所述，用 B -Tree 作为索引结构效率是非常高的。
而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的 I / O 渐进复杂度也为 O（h），效率明显比 B -Tree 差很多。
原谅我太懒了，画图很麻烦，我 copy 了很多网上优秀的解析里的图片，下面贴出链接：
https://www.cnblogs.com/nullz…
