红黑树的性质

  1. 红黑树（Red Black Tree） 是一种自平衡二叉查找树。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
  2. 二叉平衡树的严格平衡策略以牺牲建立查找结构(插入，删除操作)的代价，换来了稳定的O(logN) 的查找时间复杂度 。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除。
  3. 每个节点要么是黑色的，要么是红色的
  4. 根节点是黑色的，每个叶子结点是黑色的（注意：这里叶子节点是指为空的叶子节点）
  5. 如果一个节点是红色的，则它的子结点必须是黑色的。
  6. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

RBT的操作代价

  1. 查找代价：由于红黑树的性质（最长路径长度不超过最短路径长度的2倍），可以说明红黑树虽然不像AVL一样是严格平衡的，但平衡性能还是要比BST要好。其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。
  2. 插入代价：RBT插入结点时，需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转，这一点和AVL的插入操作一样。虽然变色操作需要O(logN)，但是变色操作十分简单，代价很小。
  3. 删除代价：RBT的删除操作代价要比AVL要好的多，删除一个结点最多只需要3次旋转操作。
  4. RBT 效率总结 : 查找 效率最好情况下时间复杂度为O(logN)，但在最坏情况下比AVL要差一些，但也远远好于BST。插入和删除操作改变树的平衡性的概率要远远小于AVL（RBT不是高度平衡的）。因此需要的旋转操作的可能性要小，而且一旦需要旋转，插入一个结点最多只需要旋转2次，删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN)，但是实际上，这种操作由于简单所需要的代价很小。
  5. 红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是AVL所不具备的。

RBT的插入和删除

  1. 插入操作：
    （1）插入根节点（不需要操作）
    （2）父节点为黑色(不需要操作)
    （3）父节点和兄弟节点为红色，祖父节点为黑色，只需要变色，将祖父节点递归检查（原本检查自己）
    （4）父节点为红色，兄弟节点为黑色，祖父节点为红色，先两次旋转再调整颜色（左旋+右旋）
  2. 删除操作：
    （1）删除只有一个新的根节点（直接删除）
    （2）父节点为黑色，兄弟节点为红色（先旋转成左左，再删除）
    （3）父节点为黑色，兄弟节点为黑色（先将兄弟节点换成红色，变成情况2）
    （4）父节点为红色，自己和兄弟节点为黑色（将父节点变成黑色，兄弟节点变成红色，变成情况2）
    （5）兄弟节点为黑色，兄弟节点左子树根节点为红色（交换颜色，旋转成为左左）
    （6）情况2和情况5，调整性质5（将N删掉，用子节点顶替，若子节点为红色，则重绘为黑色）

B+树

  1. B+树是一种平衡查找树，一个B+树有以下特征：
    （1）有n个子树的中间节点包含n个元素，每个元素不保存数据，只用来索引，所有数据都保存在叶子节点
    （2）所有叶子节点包含元素的信息以及指向记录的指针，且叶子节点按关键字自小到大顺序链接
    （3）所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
  2. 所有的数据都在叶子节点，且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序的链表。为什么要有序呢？其实是为了范围查询
  3. 以下为B+树的优势：
    （1）单一节点存储更多元素，减少IO
    （2）所有查询都要找到叶子节点，查询稳定
    （3）所有叶子节点形成有序链表，方便范围查询
  4. 聚集索引是按表的主键构造的B+树，叶子节点存放的为整张表的行记录数据，每张表只能有一个聚集索引。优化器更倾向采用聚集索引。因为直接就能获取行数据。聚集索引是物理地址连续存放的索引，在取区间的时候，查找速度非常快，但同样的，插入的速度也会受到影响而降低。聚集索引的物理位置使用链表来进行存储。
  5. 辅助索引也叫非聚集索引，叶子节点除了键值以外还包含了一个bookmark，用来告诉InnoDB在哪里可以找到对应的行数据，InnoDB的辅助索引的bookmark就是相对应行数据的聚集索引键。也就是先获取指向主键索引的主键，然后通过主键索引来找到一个完整的行。