红黑树是怎么发明的

红黑树

红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。
2-3 树是 3 阶 B 树，2-3-4 树是 4 阶 B 树

理解红黑树一句话就够了：红黑树就是用红链接表示3-结点的2-3树。那么红黑树的插入、构造就可转化为2-3树的问题，即：在脑中用2-3树来操作，得到结果，再把结果中的3-结点转化为红链接即可。而2-3树的插入，前面已有详细图文，实际也很简单：有空则插，没空硬插，再分裂。 这样，我们就不用记那么复杂且让人头疼的红黑树插入旋转的各种情况了。只要清楚2-3树的插入方式即可。

2-3-4树

由于2-3-4树是一颗阶数为4的B树，所以它会存在以下节点：

• 2节点
• 3节点
• 4节点

2节点中存放着一个key[X]，两个指针，分别指向小于X的子节点和大于X的子节点；3节点中存放在两个key[X,Y],三个指针，分别指向小于X的子节点，介于X~Y之间的子节点和大于Y的子节点；4节点可依此类推。

2-3-4树到红黑树的转化
红黑树是对概念模型2-3-4树的一种实现，由于直接进行不同节点间的转化会造成较大的开销，所以选择以二叉树为基础，在二叉树的属性中加入一个颜色属性来表示2-3-4树中不同的节点。

2-3-4树中的2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以红节点+黑节点的方式存在，红节点的意义是与黑色父节点结合，表达着2-3-4树中的3，4节点。

（此处理解成红节点也好，红色链接也好，看个人喜好。很多书中会说是由黑色节点指出的红色链接，链接指向的节点颜色为红。）

我们先看2-3-4树到红黑树的节点转换。2节点直接转化为黑色节点；3节点这里可以有两种表现形式，左倾红节点或者右倾红节点。而4节点被强制要求转化为一个黑父带着左右两个红色儿子。

本文的研究主体是2-3树（原因会在后文给出），并且是2-3树中较为特殊的一种转化–左倾红黑树。顾名思义，左倾红黑树限制了如果在树中出现了红色节点，那么这个节点必须是左儿子。
【2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点】
2-3树到红黑树的转化（左倾红黑树）

光看单个节点的转化可能还不够明显，我制作了一张红黑树转2-3树的示意图，很清晰地描绘了它们之间的关系。

只要把左倾红黑树中的红色节点顺时针方向旋转45°使其与黑父平行，然后再将它们看作一个整体，你就会发现，这不就是一颗2-3树吗？

至此，我想大家已经明白，红黑树其实就是对概念模型2-3树（或者2-3-4树）的一种实现。

算法导论中给出的是红黑树基于2-3-4树实现，其中4节点要求平衡（即4节点必须用黑色父亲和左右两个红色儿子表示，红色儿子不能出现在同一边）。

算法4中给出的红黑树是基于2-3树实现，而且这种实现的红黑树十分特殊，它要求概念模型中的3节点在红黑树中必须用左倾的红色节点来表示。这种限定能够很大的减少红黑树调整过程中的复杂性，我们将在接下来的内容中体会到这一点。

我将算法导论和算法4中的红黑树反复的看了几遍，最终选择算法4中的红黑树做演示主体。

首先，算法4中的红黑树基于2-3树概念模型，不用考虑2-3-4树中复杂的4节点分裂；

第二，算法4中的红黑树是左倾红黑树，进一步降低了调平的难度；

第三，算法导论中对于红黑树删除场景的阐述并不够具体，许多关键环节都用“经过一定的旋转和变色处理”来带过，不利于新手的学习。（我花了很长时间还原具体过程）。

考虑到部分读者有充足的精力研究以2-3-4树为概念模型的红黑树，在介绍2-3树的同时也会带上2-3-4树的基础知识，帮助学有余力的读者去理解算法导论中的红黑树。（所以如果没有必要，只看2-3树的部分就行）。

我们在了解红黑树的插入删除操作之前，需要先了解2-3树的插入删除操作，这样才能理解红黑树中染色和旋转背后的意义。

让我们来看一下对于2-3树的插入。我们的插入操作需要遵循一个原则：先将这个元素尝试性地放在已经存在的节点中，如果要存放的节点是2节点，那么插入后会变成3节点，如果要存放的节点是3节点，那么插入后会变成4节点（临时）。然后，我们对可能生成的临时4节点进行分裂处理，使得临时4节点消失。


事实上，这正对应了红黑树在插入的时候一定会把待插入节点涂成红色，因为红色节点的意义是与父节点进行关联，形成概念模型2-3树中的3节点或者临时4节点。

而红黑树之所以需要在插入后进行调整，正是因为可能存在着概念模型中的临时4节点（反应在红黑树中是双红的情况）。

试想在2-3树中如果待插入节点是个2节点，那么反应在红黑树中，不正好对应着黑色父节点吗，在黑色父节点下面增加一个红色儿子，确实不会违背红黑树的任何规则，这也对应着我们向2-3树中的2节点插入一个元素，只需要简单的把2节点变成3节点。

接下来让我们来看一下对于2-3树的删除。对于2-3树的删除我们主要要考虑待删除元素在2节点这种情况，因为如果待删除元素在3节点，那么可以直接将这个元素删除，而不会破坏2-3树的任何性质（删除这个元素不会引起高度的变化）。

当待删除元素在2节点的时候，由于删除这个元素会导致2节点失去自己唯一的元素，引发2节点自身的删除，会使得树中某条路径的高度发生变化，树变得不平衡。

因此我们有两种方案去解决这个问题：

第一种方案，先删除这个2节点，然后对树进行平衡调整。

第二种方案，我们想办法让这个被删除的元素不可能出现在2节点中。

本文选择第二种方案，我们在搜索到这个节点的路径中，不断地判断当前节点是否为2节点，如果是，就从它的兄弟节点或者它的父节点借一个元素，使得当前节点由2节点成为一个3节点或者一个临时4节点（视具体情况而定，在后面的红黑树部分会详细介绍）。

这种操作会产生一种结果：除非当前节点是根节点，否则当前节点的父节点一定是一个非2节点（因为搜索的路径是自上而下，父节点已经进行过了这种操作，所以不可能是2节点），那么我们可以保证到达叶子节点的时候，也能顺利的从父节点或者兄弟节点处借到元素，使得自己成为非2节点。从而能够直接删除某个元素（现在这个元素不在2节点中了）。

B树、B+树 、红黑树的概念及区别

B树
B树是一种自平衡的搜索树，广泛应用于文件系统和数据库中。B树的特点是：

根节点至少有两个子节点；
除根节点和叶子节点外，每个节点至少有m个子节点，其中m称为B树的阶；
所有叶子节点都在同一层；
每个节点存储的关键字个数必须满足：

其中，n为该节点存储的关键字个数。 B树相比于二叉搜索树，能够更快地进行查找、插入、删除等操作，因为B树每个节点可以存储多个关键字，而不是只能存储一个。
B+树
B+树是在B树的基础上进行了优化，也是一种自平衡的搜索树，常用于数据库和操作系统的文件系统中。B+树和B树的区别在于：

B+树的非叶子节点不存储数据，只存储关键字和指向子树中最小关键字的指针；
B+树的叶子节点存储的是所有关键字的信息，同时按照大小顺序链接起来，方便范围查找和遍历；
B+树的叶子节点的指针指向下一个叶子节点，形成了一个链表结构。 B+树相比于B树，能够更快地进行范围查询和遍历操作，因为B+树的叶子节点形成了一个链表结构。
红黑树
红黑树是一种自平衡的二叉搜索树，它是B树的一种变种，常用于C++ STL中的map和set容器实现。红黑树具有以下特点：

每个节点不是红色就是黑色；
根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL节点）；
如果一个节点是红色的，则它的子节点必须是黑色的；
从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。 红黑树的插入、删除、查找等操作的时间复杂度都是O(log n)，因此在实际应用中被广泛使用。
区别
B树和B+树是多叉树，每个节点都可以存储多个关键字，适合磁盘等外存储器的场景。B+树相比于B树，更适合范围查询和遍历操作。 红黑树是二叉树，每个节点只能存储一个关键字，适合内存等快速存储器的场景。红黑树相比于B树和B+树，更适合实现map和set这类容器。

二分查找

给定一个1~100的自然数，给你5次机会，你能猜中这个数字吗？
你会从多少开始猜？
  为什么一定是50呢？这个就是二分查找的一种思想，也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。
  所以第一个，既然索引是有序的，我们可以考虑用有序数组作为索引的数据结构。
  有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变index），所以只适合存储静态的数据。
  为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。
  所以，有没有可以使用二分查找的链表呢？
  为了解决这个问题，BST（Binary [ˈbaɪnəri] Search Tree）也就是我们所说的二叉查找树诞生了。

二叉查找树

BST Binary Search Tree 二叉查找树的特点：左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。

二叉查找树既能够实现快速查找，又能够实现快速插入。
  但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成O(n)。
  什么情况是最坏的情况呢？
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、6、11、13、17、22。
  这个时候BST会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

  造成它倾斜的原因是什么呢？
  因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

平衡二叉树–左旋右旋

AVL Trees (Balanced binary search trees)
  平衡二叉树的定义：左右子树深度差绝对值不能超过1。
  是什么意思呢？比如左子树的深度是2，右子树的深度只能是1或者3。
  这个时候我们再按顺序插入1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。

  那AVL树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过1呢？
  https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
  插入1、2、3。
  当我们插入了1、2之后，如果按照二叉查找树的定义，3肯定是要在2的右边的，这个时候根节点1的右节点深度会变成2，但是左节点的深度是0，因为它没有子节点，所以就会违反平衡二叉树的定义。
  那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把2提上去，这个操作叫做左旋。

同样的，如果我们插入7、6、5，这个时候会变成左左型，就会发生右旋操作，把6提上去。

所以为了保持平衡，AVL树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？
  在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？
  它应该存储三块的内容：
  第一个是索引的键值。比如我们在id上面创建了一个索引，我在用where id =1的条件查询的时候就会找到索引里面的id的这个键值。
  第二个是数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
  第三个，因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于26的时候，走右边，到下一个树的节点，继续判断。

当我们用树的结构来存储索引的时候，因为拿到一块数据就要在Server层比较是不是需要的数据，如果不是的话就要决定走左子树还是右子树，再读一一个节点。访问一个树的节点就是一次磁盘的I/O操作。
  因为InnoDB操作磁盘的最小的单位是一页（或者叫一个磁盘块），page的默认大小是16KB(16384字节)。那么，读取一个树的节点就是读取16KB的大小。
如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到16384个字节的容量。所以访问一个树节点，进行一次I/O的时候，浪费了大量的空间。
  所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多的节点，意味着跟磁盘交互次数就会过多。
  如果是机械硬盘时代，每次从磁盘读取数据需要10ms左右的寻址时间，交互次数越多，消耗的时间就越多。

比如上面这张图，我们一张表里面有6条数据，当我们查询id=37的时候，要查询两个子节点，就需要跟磁盘交互3次，如果我们有几百万的数据呢？这个时间更加难以估计。
  所以我们的解决方案是什么呢？
  第一个就是让每个节点存储更多的数据，充分利用16KB的大小，这样读取一个节点就能对比更多数据，较少对比次数。
  第二个，节点上的关键字的数量越多，我们的指针数也越多，也就是意味着可以有更多的分叉（我们把它叫做“路数”）。
  因为分叉数越多，树的深度就会减少（根节点是0）。
  这样，我们的树是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的样子？
  这个时候，我们的树就不再是二叉了，而是多叉，或者叫做多路。

多路平衡查找树(B树)-分裂合并

（Balanced Tree）
  这个就是我们的多路平衡查找树，叫做B Tree（B代表平衡）。
  跟AVL树一样，B树在枝节点和叶子节点存储键值、数据地址、节点引用。
  它有一个特点：分叉数（路数）永远比关键字数多1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。

B Tree的查找规则是什么样的呢？
  比如我们要在这张表里面查找15。
  因为15小于17，走左边。
  因为15大于12，走右边。
  在磁盘块7里面就找到了15，只用了3次IO。

这个是不是比AVL 树效率更高呢？
  那B Tree又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟AVL树有什么区别？
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  比如Max Degree（路数）是3的时候，我们插入数据1、2、3，在插入3的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有4个指针，子节点会变成4路，所以这个时候必须进行分裂（其实就是B+Tree）。把中间的数据2提上去，把1和3变成2的子节点。
  如果删除节点，会有相反的合并的操作。
  注意这里是分裂和合并，跟AVL树的左旋和右旋是不一样的。
  我们继续插入4和5，B Tree又会出现分裂和合并的操作。

从这个里面我们也能看到，在更新索引的时候会有大量的索引的结构的调整，所以解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。
  节点的分裂和合并，其实就是InnoDB页（page）的分裂和合并。

B+树

加强版多路平衡查找树
  因为B Tree的这种特性非常适合用于做索引的数据结构，所以很多文件系统和数据库的索引都是基于B Tree的。
  但是实际上，MySQL里面使用的是B Tree的改良版本，叫做B+Tree（加强版多路平衡查找树）。

B+树的存储结构：

MySQL中的B+Tree有几个特点：

它的关键字的数量是跟路数相等的；
B+Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储。搜索到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索id=28，虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶子节点。
B+Tree的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。

总结一下， B+Tree的特点带来的优势：

它是B Tree的变种，B Tree能解决的问题，它都能解决。B Tree解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵B+Tree拿到所有的数据）
B+Tree的磁盘读写能力相对于B Tree来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
效率更加稳定（B+Tree永远是在叶子节点拿到数据，所以IO次数是稳定的）

参考文章
https://mp.weixin.qq.com/s/sPIE54UmvNgINZIATQKyew
https://blog.csdn.net/qq_38526573/article/details/109550971
https://blog.csdn.net/fei33423/article/details/79132930