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

索引数据结构

一、二叉树

二叉查找数的性能其实并不稳定，导致这个结果的原因就是二叉查找树的对称性，二叉查找树的对称性并不稳定，在极端的情况下，可能出现树的高度跟键的数量相同，也就是最坏的情况，查找和插入算法的时间复杂度跟键的数量将呈现线性关系。

二、红黑树

红黑树是一个稳定的平衡二叉树，但是mysql并没有选择红黑树作为查找数据的索引，主要原因考虑到数据量在过大时会出现树的高度很高，导致比较的次数增多，伴随的IO次数也会相应的增多，从而导致查询效率很慢。另外，每次新增删除数据都有可能导致索引结构产生变化，增加了索引的维护成本。

三、Hash表

Hash表的存储结构是数组+链表，对数据进行hash求hash槽位，将数据落到对应的hash槽，从查询具体单条数据是非常快的，但是如果是范围查找，Hash表就显得力不从心，它根本满足不了

四、B-Tree

我们知道mysql在磁盘中存储的数据是按照一页一页存储的，一页的大小为16kb。B-Tree如图，按照正常的数据存储，假设data的大小为1kb，忽略间隙中存储的指针，那么一页可以存储16条数据，存储1000万条数据，树的高度大约为6层，而红黑树的高度将达到20多层，B-Tree相对于红黑树已经提升了几倍，但是mysql并没有使用B-Tree作为索引的数据结构，而是对B-Tree进行优化，产生了B+Tree

 B+Tree （B-Tree变种）

从数据结构的结构来看，B-Tree在每个节点上都存储了data而且索引的key不重复；而B+Tree只在叶子结点上存储数据，非叶子节点只存储key值并且非叶子节点上的key值在叶子结点上重复存储，还有相邻的叶子结点互相存储一个指针。同样存储1000万条数据B+Tree只需要3层树的高度即可，mysql使用的就是B+Tree数据结构作为索引。

B+Tree比较B-Tree的优点

1、存储相同的数据，树的高度低；忽略key值在内存中的比较，B+Tree的IO次数只需要一次（索引常驻内存），B-Tree可能1-6次。

2、B+Tree叶子结点的页磁盘指针很适合范围查找，只要拿到最小和最大值就可以通过指针快速查找。

MyISAM索引文件和数据文件是分离的(非聚集)

 InnoDB索引实现

1、聚集索引 

 2、非聚集索引

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

如果程序员建表时不建主键，mysql会帮助我们建唯一主键，相当于增加了mysql的工作。整型主要为了新增数据时创建索引方便比较，自增是为了不影响之前已经创建好的索引结构；提高新增数据时插入索引的效率；在分库分表中可以更好的映射到数据所存储的数据库中。

联合索引

 联合索引的特点，第一个字段为有序的，第二个字段在第一个字段相同情况下是有序的，第三个字段在前两个字段都有序时才是有序的。这就是为什么使用联合索引时需要满足最左侧原则。