数据库索引

什么是聚集索引，非聚集索引，索引覆盖，回表，索引下推
如何理解Mysql的索引及他们的原理？
为什么mysql用B+树做索引而不用B-树或红黑树
数据库索引（B树，B+树，哈希）

二叉树

对于查找，我们很容易想到二叉查找树，但是二叉查找树查找效率不稳定，时间可能在O(logn) - O(n),O(n)为二叉查找树为链表的时候

平衡二叉查找树

平衡二叉查找树满足，左子树的值都小于根节点的值，右子树的值都大于根节点的值。且左右子树的高度差不大于1。这样查找的复杂度就是O(logn)，但是二叉查找树的一个节点只有左右两个子节点，如果数据量多，会造成树的高度非常庞大

B树

image.png

B树可以有不止两个子节点，B树一个节点包含了子节点的磁盘地址，主键的值，还有行数据。

B树有两个不好的地方

1. 查询效率不稳定
2. B树每个节点都有data，因为节点都是存在磁盘里的，每次从磁盘里只能一页一页地读，B树多了个data指针，无疑会加大磁盘的消耗，读一次数据就减少读到节点的数目 (（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时）)
3. B树做范围查询比较难

B+树

B+树相对于B树有几点不同：

image.png

1. 非叶子节点只存储键值和指针。
2. 所有叶子节点之间都有一个链指针。
3. 数据记录都存放在叶子节点中。

B+树相对B树的优点

1. B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有Data域。
2. B+树所有的Data域在叶子节点，并且所有叶子节点之间都有一个链指针。 这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。在数据库中基于范围的查询是非常频繁的，而B树不支持这样的遍历操作。

缺点：

1. B+树对查询的优化操作会降低了一定写入性能。

聚集索引

在MySQL中，选定主键之后将会自动为主键创建索引。该索引可以维护主键的唯一性。非叶子节点包含了主键值，而叶子节点则指向了一条完整的记录

非聚集索引

非聚簇索引为什么是二级索引呢？重点在于一个二字。可以料想如果WHERE条件不是根据主键进行索引，那么我们就需要基于该非主键建立的索引进行检索，这样建立的索引叶子节点中包含了记录的主键，再使用主键在聚簇索引中找寻到完整的记录。可以说进行了两次B+ Tree查找而不是一次