索引

数据是以文件的形式存放在磁盘上，每一行数据都有它的磁盘地址。如果没有索引的话，我们从500万条数据检索一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。
有了索引以后，只需要去索引里检索这条数据就行了。

索引类型

在这里插入图片描述
第一个是索引的名称，第二个是索引的列。还有索引类型和索引方法。
在InnoDB里面，索引类型有3种：
普通（Normal）：也叫非唯一索引，是最普通的索引
唯一（Unique）：唯一索引要求键值不能重复。主键索引是一种特殊的唯一索引，它还多了一个条件，要求主键值不能为空。主键索引用primary key创建。
全文（Fulltext）：针对比较大的数据，比如存放消息内容，解决like查询在全文匹配的时候效率低，可以创建全文索引。只有文本类型字段才可以创建全文索引。比如char、varchar、text。
MyISAM和InnoDB支持全文索引。

索引方法Btree和Hash，这个后面再说。

索引模型推演

二分法查找

有序数组等值查询效率非常高，但是只适合存储静态数据。
为了方便支持频繁修改，比如插入数据，我们采用链表。
有没有支持二分法查找的链表呢？
因此，BST（Binary Search Tree）也就是所说的二叉查找树诞生了。

二叉查找树

在这里插入图片描述

二叉查找树查找和树的深度相关，最坏的情况退化成链表，时间复杂度变为O(n)。

所以需要来限制树的深度，这就是平衡树。左右子树的深度差不超过1。

平衡二叉树（AVL Tree）（左旋、右旋）

通过左旋、右旋，树达到了平衡。但是随着数据量的增大，树的深度会变得 “瘦高”，深度变大。
在这里插入图片描述

如何降低树的高度？只能让节点有更多的分叉。
这时候我们的树不再是二叉了，而是多叉，或者叫多路。

多路平衡查找树（B Tree）（分裂、合并）

BalancedTree就是我们的多路平衡查找树，叫做B Tree。
跟AVL树一样，B树在枝节点和叶子结点存储值、数据地址、节点引用。
它有一个特点：分叉数（路数）永远比关键字数多1。比如我们这棵树，每个节点存储2个关键字，那么就会有3个指针指向3个子节点。（当然肯定不止3个这么少）
在这里插入图片描述
B tree的查找规则如何？
比如我们要找15。
因为15小于17，走左边。
因为15大于12，走右边。
在磁盘7里面找到了15，只用了3次磁盘IO。

B Tree通过分裂和合并来维持平衡：
比如Max Degree（路数）是3 的时候，我们插入数据1、2、3，在插入3 的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有4 个指针，子节点会变成4 路，所以这个时候必须进行分裂。把中间的数据2 提上去，把1 和3 变成2 的子节点。

如果删除节点，会有相反的合并的操作。
注意这里是分裂和合并，跟AVL 树的左旋和右旋是不一样的。

我们继续插入4 和5，B Tree 又会出现分裂和合并的操作。
在这里插入图片描述
节点的分裂和合并，其实就是InnoDB 页的分裂和合并。

B+树（加强版多路平衡查找树）

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

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

在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：

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

将上面的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：
在这里插入图片描述
实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2~4层。
mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。
辅助索引与聚集索引的区别在于：
辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

为什么不用红黑树

红黑树是一颗平衡二叉树，数据量大的时候，树的深度也很深，如果树的深度有20层，而查找的数据在叶子节点，就要进行20次IO操作，性能低。
通过变色和旋转来保持平衡，有很多规则。
在这里插入图片描述
红黑树规则：

1、节点存在逻辑上的颜色：黑色和红色，根节点为黑色，

2、叶子节点为黑色的空节点，红色节点下的子节点一定为黑色节点。

3、从根节点到叶子节点所有的路径上存在相同数目的黑色节点。

4、红黑树的这些特性导致红黑树的平衡性，从根节点到叶子节点的最长路径不会超过最短路径的2倍。

索引方式：真的只有B+Tree吗

Navicat工具中，我们看到索引的方法有2种。除了BTree，还有Hash。
HASH：
以KV的形式检索数据，时间复杂度O(1)。只能支持等值查询（= in），不支持范围（between and）查找。

InnoDB聚集索引

在InnoDB的索引叶子节点上，它直接存储了我们的数据。
所以说在InnoDB中索引即数据，数据即索引，就是这个原因。

聚集索引（聚簇索引）

就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。
如果一个表创建了主键索引，那么这个主键索引就是聚集索引。
主键索引之外的索引，并不会把数据放到叶子结点。
比如我们在name上建立的普通索引。这个辅助索引也叫“二级索引”。
二级索引的叶子结点存储的是主键id的值。最终我们还是要根据主键的聚集索引拿到这一行的记录。
辅助索引为什么要存主键的值，不去存地址？
因为地址有可能会变化。
假如一张表没有主键索引怎么办？