1.红黑树

1.1.红黑树的定义和性质

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

1. 每个节点要么是黑色，要么是红色。
2. 根节点是黑色。
3. 每个叶子节点（NIL）是黑色。
4. 每个红色结点的两个子结点一定都是黑色。
5. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

1.2.红黑树的自平衡

红黑树能够实现自平衡，主要依靠以下三种操作：左旋、右旋、变色。

左旋： 以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。

右旋： 以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。

左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。
右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

变色： 结点的颜色由红变黑或由黑变红。

2.B树（多路平衡查找树）

B树是为磁盘等外存储设备设计的一种平衡查找树。系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。

我们可以将磁盘中的数据记录表示为一个[key, val]形式的二元组，key为表中的主键值，data为主键对应的数据。对于不同的记录，key值互不相同。

在B树中，我们可以将每个磁盘块看成是B树的一个节点，在每个节点中，包含着升序排序的key主键，这些key主键中包含着对应data数据，并且将指向子节点的指针分割开来，在key左边的指针指向的key值比当前key值小，右边的指针指向的key值比当前大。

如下图所示，模拟查找key为29的数据：

1. 根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】
2. 比较关键字29在区间（17,35），找到磁盘块1的指针P2。
3. 根据P2指针找到磁盘块3，读入内存。【磁盘I/O操作第2次】
4. 比较关键字29在区间（26,30），找到磁盘块3的指针P2。
5. 根据P2指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】
6. 在磁盘块8中的关键字列表中找到关键字29。

3.B+树

B+树是在B树的基础上做出的优化版本，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+树实现其索引结构。

在B树中每个节点中不仅包含数据的key值，还有data值。 而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B树深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

在B+树中：
1. 非叶子节点只存储key键值信息。
2. 所有叶子节点之间都有一个链指针。
3. 数据data记录都存放在叶子节点中。

通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+树进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

4.B树和B+树的总结

B树（B+树）都属于多路平衡查找树，在B树中，每个节点包含着多个key键值和data数据（按key值升序排列），key键值将指向子节点的指针分隔开，左边的指针指向比当前key值小的子节点，右边的指针指向比当前key值大的子节点。

B+树中将所有的data数据都放在了叶子节点，并且在叶子节点中形成了链式环结构。