一、Mysql 索引底层数据结构

索引的本质

索引就是帮助Mysql高效获取数据的排好序的数据结构。
注意红字，这两个是重点，第一是排好序，第二它是数据结构。

Mysql存储引擎

MyISAM存储引擎索引文件和数据文件是分离的，Usertabmyisam表使用的myisam存储引擎，表相关文件有三个，.frm是存放表结构数据，MYD是表数据。MYI是存放索引，索引树上会存储数据在MYD文件里面的位置。
InnoDB存储引擎Usertab使用的Innodb存储引擎，表相关文件只有两个同样.frm文件是存放表结构数据，.ibd存放的数据和索引。
表数据文件本身就是按B+Tree组织的一个索引结构文件，主键索引叶节点包含了完整的数据记录。
以InnoDB为例，B+树的存储结构为：
数据放在主键索引上面，非叶子节点不存储data

聚集索引和非聚集索引

Mysql中，不同的存储引擎对索引的实现方式不同，大致说下MyISAM和InnoDB两种存储引擎。
MyISAM的B+Tree的叶子节点上的data，并不是数据本身，而是数据存放的地址。主索引和辅助索引没啥区别，只是主索引中的key一定得是唯一的。这里的索引都是非聚簇索引，如图所示。

InnoDB的数据文件本身就是索引文件，B+Tree的叶子节点上的data就是数据本身，key为主键，这是聚簇索引。非聚簇索引，叶子节点上的data是主键。聚集索引一般是表中的主键索引，如果表中没有显示指定主键，则会选择表中的第一个不允许为NULL的唯一索引，如果还是没有的话，就采用Innodb存储引擎为每行数据内置的6字节ROWID作为聚集索引。

图解几种数据结构

首先说明一点，Mysql索引用的数据结构是B+树（极少情况下用Hash），那么为啥不用其它数据结构呢？下面我们说一下原因。
推荐工具：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html，它可以帮助我们动态演示各种数据结构。

二叉树：

如果数据是递增、单边增长的情况，那么数据结构树就会非常高大，查询效率慢。例如下图，仅仅5个数据，树的高度就到了5。

红黑树：

在二叉树基础上，多了树平衡，不像二叉树那样在极端情况下往一个方向扩展树。但是，当数据量太大的时候，这棵树的高度仍然很高，查询效率也慢。

比如下图，仅仅10个数据，树的高速就达到了4，显然也不能选红黑树作为索引数据结构。

B树：

与红黑树相比，B树的每个节点可以存放多个数据，从而降低树的高度。

其实上边这张图还不能很清晰的表现出B树，来看下图，B树的数据结构中，所有键值分布在整颗树中（索引值和具体data都在每个节点里）。任何一个关键字出现且只出现在一个结点中。

B+树：

B+树是B树的变种，它与 B- 树的不同之处在于：
①非叶子节点并不存储真正的 data
②为所有叶子结点增加了一个链指针

Hash:

hash查找很快，但是当遇到范围查找的时候hash就尴尬了，另外还有hash冲突问题。所以根据实际业务需求来看是用btree还是hash。我们日常工作绝大多情况还是用B+树。

主键索引的常见问题：

1. 为什么非主键索引结构叶子节点存储的是主键值？

一是保证一致性，更新数据的时候只需要更新主键索引树，二是节省存储空间。

1. 为什么推荐InnoDB表必须有主键？

保证会有主键索引树的存在（因为数据存放在主键索引树上面），如果没有mysql会自己生成一个rowid作为自增的主键主键索引

1. 为什么推荐使用整型的自增主键？

一是方便查找比较，二是新增数据的时候只需要在最后加入，不会大规模调整树结构，如果是UUID的话，大小不好比较，新增的时候也极有可能在中间插入数据，会导致树结构大规调整，造成插入数据变慢。

联合索引

联合索引就是几个字段一起作为索引，注意最左原则。