索引的本质

定义

索引是帮助MySQL高效获取数据的排好序的数据结构

索引数据结构

1.二叉树

二叉树特性：

右边元素大于等于父元素，左边元素小于父元素

key存储的是表中索引的值，value存储的是索引所在行的整行的地址。

通过索引找到索引所在行的地址，拿到地址之后可以获取到索引所在行的整行的数据。

如果二叉树的数据是有序的话，那么就会变成一个链表。

2.红黑树

在数据有序(单边增长)的时候会做一次平衡，红黑树也叫做平衡二叉树。

红黑树的弊端：

树的高度不确定。

3.Hash索引

对索引的key进行一次hash（例如MD5就是一种hash算法，MySLQ底层实现有 自己的Hash算法）计算就可以定位出数据存储的位置

很多时候hash索引要比B+Tree索引更高效

仅能满足‘=’ ，‘in’，不支持范围查询

hash冲突问题

MySQL在对索引的key做hash之后会丢到一个hash桶里面去

4.B-Tree

1. 叶节点具有相同的深度，叶节点的指针为空
2. 所有索引元素不重复
3. 节点中的数据索引从左到由递增排列

data元素还是key，value，key是索引的值，value是索引所在行的磁盘文件地址。

5.B+Tree(B-Tree变种)

1. 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
2. 叶子节点包含所有索引字段
3. 叶子节点用指针连接，提高区间访问的性能

非叶子节点两个索引之间存储的值是下一个非叶子节点所在的磁盘文件的地址。

查找过程：

把根节点的元素全部加载到内存中， 然后在内存中找要查找的索引所在的位置区间，然后拿到下一个非叶子节点或叶子结点的磁盘文件地址去比对。

查看MySQL文件页大小:

-- 查看MySQL文件页大小
show GLOBAL STATUS like '%innodb_page_size%'

MySQL一个节点页的大小大概是16kb。

一张表如果用int或bigint类型做主键，那么索引大小为8个字节，中间存储的下一个磁盘文件地址大概6个字节，16kb大小大概可以存储16kb/(8+6)个字节。即大概1170个元素。叶子节点根据存储类型不同，可能data存储的是索引所在行的地址，也可能存储的是索引所在行的其他列的数据，就算叶子节点数据存储为1kb，那么三层高度的B+Tree可以存储1170X1170X16大概是一千多万数据。

B+Tree在叶子节点有一个双向指针，它的节点元素是从左到右依次排好序的，那么就可以进行范围查找。

MySQL存储引擎索引实现

MySQL的data目录下的一个文件就对应一个数据库实例

其中MyISAM和Innodb存储引擎对应的表数据文件是不一样的

MyISAM存储引擎对应有三个数据文件：

.frm和.MYD和.MYI文件

.MYD存储数据

.MYI存储B+Tree组织的索引

Innodb对应两个数据文件，

.frm和.ibd文件

.ibd存储数据 和索引

存储引擎是形容数据库表的。

1.MyISAM存储引擎实现

MyISAM索引文件和数据文件是分离的(非聚集，也叫稀疏索引)

2.InnoDB存储引擎实现

InnoDB索引文件实现(聚集)

表数据文件本身就是按B+Tree组织的一个索引结构文件

聚集索引---叶子节点包含了完整的数据记录

为什么建议InnoDB表必须建主键?并且推荐使用整型的自增主键？

​ 1. 因为这些数据必须要用B+Tree来组织，如果自带主键索引，那么就可以使用主键来组织B+Tree索引。如果不建立主键索引，那么MySQL会从第一列开始，选择一列所有数据都不相等的来建立B+Tree索引。如果都没有选到，MySQL会建立一列隐藏列，类似于RowId，MySQL会维护这个RowId的唯一性，然后用这个RowId来组织整个表的B+Tree索引。

​ 所以推荐建立主键，因为MySQL的数据库资源是非常宝贵的，这些简单的事情完全可以自己完成，不必交给MySQL完成。

2. 索引如果使用字符串类型的话存储占用的内存要大一点，还有在查找索引的时候需要比对，如果不是整型的话，比对的开销比较大。
3. 如果索引是自增的话，那么在指定元素插满之后之后平衡之后再开一个节点存放下一个元素。如果是非自增的话，那么会导致分裂之后平衡然后在开一个节点，开销相对于自增的要大。

为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)

​ InnoDB整张表只会有一个聚集索引，如果你键了主键，那么它就会用主键来组织这个聚集索引，如果你没建，那么它就会选择全部不相等的那一列作为聚集索引，如果找不到，那么就会创建一个隐藏列作为聚集索引。

​ 二级索引叶子节点存储的是主键，如果是根据二级索引查找数据的话，那么在二级索引构建的B+Tree中找到主键索引的值，然后拿这个主键索引的值去一级索引(即主键索引)构建的B+Tree上去查找数据。这个操作也成为回表操作。

​ 二级索引也是非聚集索引。

索引最左前缀原则

联合索引的底层存储结构长什么样？