什么是聚集索引，非聚集索引，索引覆盖，回表，索引下推
如何理解Mysql的索引及他们的原理？
为什么mysql用B+树做索引而不用B-树或红黑树
数据库索引（B树，B+树，哈希）
二叉树
对于查找，我们很容易想到二叉查找树，但是二叉查找树查找效率不稳定，时间可能在O(logn) - O(n),O(n)为二叉查找树为链表的时候
平衡二叉查找树
平衡二叉查找树满足，左子树的值都小于根节点的值，右子树的值都大于根节点的值。且左右子树的高度差不大于1。这样查找的复杂度就是O(logn)，但是二叉查找树的一个节点只有左右两个子节点，如果数据量多，会造成树的高度非常庞大
B树
image.png
B树可以有不止两个子节点，B树一个节点包含了子节点的磁盘地址，主键的值，还有行数据。
B树有两个不好的地方
- 查询效率不稳定
- B树每个节点都有data，因为节点都是存在磁盘里的，每次从磁盘里只能一页一页地读，B树多了个data指针，无疑会加大磁盘的消耗，读一次数据就减少读到节点的数目 (（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时）)
- B树做范围查询比较难
B+树
B+树相对于B树有几点不同：
image.png
- 非叶子节点只存储键值和指针。
- 所有叶子节点之间都有一个链指针。
- 数据记录都存放在叶子节点中。
B+树相对B树的优点
- B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。
- B+树所有的Data域在叶子节点，并且所有叶子节点之间都有一个链指针。 这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。
缺点：
- B+树对查询的优化操作会降低了一定写入性能。
聚集索引
在MySQL中，选定主键之后将会自动为主键创建索引。该索引可以维护主键的唯一性。非叶子节点包含了主键值，而叶子节点则指向了一条完整的记录
非聚集索引
非聚簇索引为什么是二级索引呢？重点在于一个二字。可以料想如果WHERE条件不是根据主键进行索引，那么我们就需要基于该非主键建立的索引进行检索，这样建立的索引叶子节点中包含了记录的主键，再使用主键在聚簇索引中找寻到完整的记录。可以说进行了两次B+ Tree查找而不是一次
