索引是帮助MySQL高效获取数据的排好序的数据结构，由于以上实现的数据结构与数据库中索引相关，关于索引，有以下知识：
- 唯一索引：唯一索引不允许两行具有相同的索引值
- 主键索引：为表定义一个主键将自动创建主键索引，主键索引是唯一索引的特殊类型。
主键索引要求主键中的每个值是唯一的，并且不能为空 - 聚集索引（Clustered)：表中各行的物理顺序与键值的逻辑（索引）顺序相同，每个表只能有一个
- 非聚集索引（Non-clustered)：非聚集索引指定表的逻辑顺序。
数据存储在一个位置，索引存储在另一个位置，索引中包含指向数据存储位置的指针可以有多个（小于 249 个）
索引数据结构#
二叉树#
左边子节点的数据小于父节点数据，右边子节点的数据大于父节点数据。如果col2是索引，查找索引为89的行元素，那么只需要查找两次，就可以获取到行元素所在的磁盘指针地址。
如果col1是索引，查找索引为6的行元素，那么需要查找六次，就可以获取到行元素所在的磁盘指针地址，即得到了该索引为6的行元素。因此二叉树不适合存储单边增长的序列字段，近乎全表扫描获取数据。
红黑树#
本质二叉树，属于二叉平衡树，jdk1.8 hashmap的底层实现；存储大数据量，树的高度不可控， 数量越大，树的高度越高；500w行数据，2的n次方=500w数据量， n是树的高度，也就是查询次数；
hash表#
通过散列可以快速获取磁盘文件指针，对于指定索引查找文件非常快，但是对于范围查找没法支持。
B树#
本质是多路二叉树；叶节点具有相同的深度，叶节点的指针为空；所有索引元素不重复；节点中数据索引从左到右依次递增的；
B+树（B树的变种）#
非叶子节点不存储数据，只存储索引(冗余)和指针，可以放更多的索引，树高降低 ；叶子节点包含所有索引字段；叶子节点比b树增加了指针连接；叶子节点有双向指针链接(首尾子节点还通过指针连接)，提高区间访问的性能，范围查找；
为什么mysql页文件默认16K？
MySQL每个B+树节点最大存储容量：16KB （指针+数据+索引）。假设我们一行数据大小为1K，那么一页就能存16条数据，也就是一个叶子节点能存16条数据；再看非叶子节点，假设主键ID为bigint类型，那么长度为8B，指针大小在Innodb源码中为6B，一共就是14B，那么一页里就可以存储16K/14=1170个(主键+指针)那么一颗高度为2的B+树能存储的数据为：117016=18720条，一颗高度为3的B+树能存储的数据为：11701170*16=21902400（千万级条）
1 | show global status like `Innodb_page_size` |
因此，B+树存储大数据量的表也可以非常高效的获取数据，MySQL使用B+树作为索引的数据结构。
存储引擎#
InnoDB（聚集）#
表数据文件本身是按照B+tree组织的一个索引结构文件frm文件：存储这张表的表结构ibd文件：存储这张表的所有数据行和索引字段聚集(聚簇)索引----叶节点包含完整数据记录
为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？
首先，为了满足MySQL的索引数据结构B+树的特性，必须要有索引作为主键，可以有效提高查询效率，因此InnoDB必须要有主键。如果不手动指定主键，InnoDB会从插入的数据中找出不重复的一列作为主键索引，如果没找到不重复的一列，InnoDB会在后台增加一列rowId做为主键索引。
其次，索引的数据类型是整型，一方面整型占有的磁盘空间或内存空间相比字符串更少，另一方面整型比较比字符串比较更快速，字符串比较是先转换为ASCII码，然后再比较的。
最后，B+树本质是多路多叉树，如果主键索引不是自增的，那么后续插入的索引就会引起B+树的其他节点的分裂和重新平衡，影响数据插入的效率，如果是自增主键，只用在尾节点做增加就可以。
为什么非主键索引结构叶子节点存储的是主键值？
主键索引和非主键索引维护各自的B+树结构，当插入的数据的时候，由于数据只有一份，通过非主键索引获取到主键值，然后再去主键索引的B+树数据结构中找到对应的行数据，节省了内存空间；
如果非主键索引的叶子节点也存储一份数据，如果通过非主键索引插入数据，那么要向主键索引对应的行数据进行同步，那么会带来数据一致性问题。可以通过事务的方式解决，我们都知道使用事务后，就会对性能有所消耗。
联合索引
两个或更多个列上的索引被称作联合索引，联合索引又叫复合索引。对于复合索引:Mysql从左到右的使用索引中的字段，一个查询可以只使用索引中的一部份，但只能是最左侧部分。
例如索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种组合进行查找，但不支持 b,c进行查找 .当最左侧字段是常量引用时，索引就十分有效。
MyISAM和InnoDB的9大区别#
- InnoDB支持事务，MyISAM不支持，对于InnoDB每一条SQL语言都默认封装成事务，自动提交，这样会影响速度，所以最好把多条SQL语言放在begin和commit之间，组成一个事务；
- InnoDB支持外键，而MyISAM不支持。对一个包含外键的InnoDB表转为MYISAM会失败；
- InnoDB是聚集索引，使用B+Tree作为索引结构，数据文件是和（主键）索引绑在一起的（表数据文件本身就是按B+Tree组织的一个索引结构），必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。MyISAM是非聚集索引，也是使用B+Tree作为索引结构，索引和数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的。也就是说：InnoDB的B+树主键索引的叶子节点就是数据文件，辅助索引的叶子节点是主键的值；而MyISAM的B+树主键索引和辅助索引的叶子节点都是数据文件的地址指针。
- InnoDB不保存表的具体行数，执行select count(*) from table时需要全表扫描。而MyISAM用一个变量保存了整个表的行数，执行上述语句时只需要读出该变量即可，速度很快；
- Innodb不支持全文索引（5.7以后支持），而MyISAM支持全文索引，查询效率上MyISAM要高
- MyISAM表格可以被压缩后进行查询操作
- InnoDB支持表、行(默认)级锁，而MyISAM支持表级锁InnoDB的行锁是实现在索引上的，而不是锁在物理行记录上。潜台词是，如果访问没有命中索引，也无法使用行锁，将要退化为表锁。
- InnoDB表必须有主键（用户没有指定的话会自己找或生产一个主键），而Myisam可以没有
- Innodb存储文件有frm、ibd，而Myisam是frm、MYD、MYIInnodb：frm是表定义文件，ibd是数据文件Myisam：frm是表定义文件，myd是数据文件，myi是索引文件
扩展阅读#
- MySQL索引背后的数据结构及算法原理 http://blog.codinglabs.org/articles/theory-of-mysql-index.html