B树、B+树和红黑树
B树
2-3树和2-3-4树
多路查找树，其每个节点的孩子数可以多于两个，且每一个结点处可以存储多个元素，所有的元素之间存在某种特定的排序关系。
- 首先聊一聊2-3树：
-
每个节点具有两个孩子（2结点）或 三个孩子（3结点）
-
2结点具有一个元素和两个孩子（或没有孩子），左子树元素小于该元素，右子树元素大于该元素。这个2节点要么没有孩子，要有就有两个，不能只有一个孩子。
-
3结点具有两个元素和三个孩子（或没有孩子），左子树元素小于较小元素，右子树元素大于较大元素，中子树包含介于两元素之间的元素。这个3节点要么没有孩子，要有就有3个。
-
2-3树中的所有叶子都在一个层次上。
同理，2-3-4树是2-3树的拓展，包括了4结点的使用。一个4结点包含了小中大三个元素和四个孩子（或没有孩子）
而2-3树和2-3-4树都是B树的特例
2-3树的插入和删除
- 再聊一聊2-3树的插入和删除操作
插入操作：与二叉排序树相同，插入操作一定是发生在叶子结点的。
-
对于空树，直接插入一个2结点
-
对于2结点的插入：直接将2结点转换为3结点即可
-
对于3结点的插入一个新元素：因为3结点本身已经是2-3树结点的最大容量，因此需要将其拆分，将树中两元素或插入元素的三者中选择其一向上移动一层。
例如插入元素5，需要将6向上移动一层
删除操作：
-
所删除元素位于一个3结点的叶子节点上，直接将该节点删除
-
所删除的元素位于一个2结点的叶子节点上，分为4种情况
- 此节点的父结点也是2结点，且拥有一个3结点的右孩子
例如删除结点1，只需要进行左旋，让6成为父节点，4成为6的左孩子，7为6的右孩子
- 此节点的父结点也是2结点，且拥有一个2结点的孩子
-
此节点的父结点是3结点
-
当前树是一颗满二叉树
- 所删除元素位于非叶子结点。此时通常是将树按中序遍历后得到此元素的前驱或后继元素，考虑让他们来补位即可
描述一颗B树时需要指定它的阶数
每一个结点都可以存储多个数据，我们可以进一步的将其细分为
B+树
B+树的优点
-
单一节点存储更多的元素，使得查询的IO次数更少。
-
所有查询都要查找到叶子节点，查询性能稳定。
-
所有叶子节点形成有序链表，便于范围查询。（并且B树和B+树的结点是按照顺序进行存储的）
B+树和B树的区别
- B树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
- B+树相邻的叶子节点之间是通过链表指针连起来的，B树却不是。
- 查找过程中，B树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
- B树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。
为什么索引结构默认使用B+树，而不是B-Tree，Hash哈希，二叉树，红黑树？
简单版回答如下：
- Hash哈希，只适合等值查询，不适合范围查询。
- 一般二叉树，可能会特殊化为一个链表，相当于全表扫描。
- 红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。
- B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。
红黑树
红黑树与2-3树间的关系
红黑树是对2-3-4树的一种实现。
在2-3-4树中加入一个颜色属性来表示2-3-4树中的不同结点。2-3-4树中的2节点对应着红黑树中的黑色节点，而2-3-4树中的非2节点是以红节点+黑节点的方式存在
- 2结点直接转换为黑色结点
- 3结点这里有两种转换方式：左倾红节点和右倾红节点
- 4结点被转换为一个黑色父节点带着两个左右红色孩子
本文的研究主体是2-3树（原因会在后文给出），并且是2-3树中较为特殊的一种转化–左倾红黑树。顾名思义，左倾红黑树限制了如果在树中出现了红色节点，那么这个节点必须是左儿子。
可以将红黑树转换为2-3树
红黑树的5条特性
- 结点颜色有红色和黑色
- 根结点必为黑色
- 2-3树种如果根节点为2结点，那么它本来就对应红黑树种黑节点；如果根节点为3结点，也可以将转换为左倾红黑树，黑色结点为父节点，黑结点表示较大的元素
- 所有叶子结点都是黑色
- 此处提到的叶子其实是空链接
- 任意结点到每个叶子结点经过的黑色结点数目都相同 –>根节点到每个叶子结点经过的黑色结点数目都相同
- 红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡
- 不会有连续的红色结点
- 2-3树中本来就规定没有4节点，2-3-4树中虽然有4节点，但是要求在红黑树中体现为一黑色节点带两红色儿子，分布左右，所以也不会有连续红节点
变色和旋转
- 变色：将黑色结点变为红色结点，或将红色结点变为黑色结点；可以参考2-3树的插入操作，本质上就是将其中一个元素上移一层
- 旋转：可以参考2-3的删除操作，
左倾红黑树的插入操作
-
如果待插入的结点比黑父小，这种情况不会破坏红黑树的规则，直接在插入即可。
以下三种情况都会对原来的红黑树进行调整
-
第一种，待插入元素比黑父大
插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。 注意，这种情况对应着2-3树中出现了临时4节点，我们在2-3树中的处理是将这个临时4节点分裂，左右元素各自形成一个2节点，中间元素上升到上层跟父节点结合。
所以，我们在红黑树中的动作是，将原本红色的左右儿子染黑（左右分裂），将黑父染红（等待上升结合）。
-
第二种情况，待插入元素比红父小，且红父自身就是左倾。
听起来有点绕，看图就会明白，其实就是说红父和待插入元素同时靠在了左边，形成了连续的红节点。
这种情况我们需要用两步来调整。由于我们插入的是红色节点，其实不会破坏黑色完美平衡，所以要注意的是在旋转和染色的过程种继续保持这种完美黑色平衡。
S首先对红父的父亲进行一次右旋，这次右旋不会破坏黑色平衡，但是也没有解决连续红色的问题。 接下来将12所在节点与15所在节点交换颜色，这样的目的是为了消除连续红色，并且这个操作依旧维持了黑色平衡。现在我们已经得到了情况1的场景，直接按情况1处理即可。
-
第三种情况，待插入元素比红父大，且红父自身就是左倾。 也就是说插入的这个节点形成了一个右倾的红色节点，对右倾的处理很简单，将红父进行一次左旋，就能使得右倾红节点变为左倾，现在出现了连续的左倾红节点，直接按情况2处理即可。
左倾红黑树的删除操作
…
讨论
- 为什么用红黑树而不用2-3树呢？其实是因为在C语言的数据结构上，实现2-3-4 tree比较啰嗦，使用二叉树更容易实现
- 二叉查找树(查询时间不稳定)->avl树(增删时间不稳定) -> 红黑树 逐步变为查询与增删消费时间均衡的数据结构 ？
红黑树的各种操作的时间复杂度是多少？
能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）
红黑树相比于BST和AVL树有什么优点？
红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。
相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，所以在插入和删除中所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的