什么是索引
索引是帮助mysql高效获取数据的排好序的数据结构
索引的存储
InnoDb, 表结构的定义存储在[表名.frm]中，索引和数据存储在[表名…ibd]文件中
索引的分类
- 数据结构角度
- B+Tree
- Hash
- 物理存储角度
- 聚簇索引（主键索引）
- 非聚簇索引（二级索引）
- 逻辑角度
- 主键索引
- 唯一索引
- 单列索引
- 联合索引
索引结构
数据结构角度
B+Tree
问：为什么Mysql用B+Tree树作为索引的数据结构？
答： 因为数据库需要支持范围查找，同时要尽量控制每次查询过程中磁盘I/O的次数，即需要控制树高。
二叉树、红黑树
每层存储的元素较少，同样数据量的情况下，相比与B树和B+树，树高太高，导致每次查询过程中的I/O次数不可控可，大部分情况下I/O次数过多。
B树：
- 非叶子节点也存储了数据，Mysql以页为单位存储和读取数据，每页大小16KB，由于非叶子节点也存储了数据，导致在非叶子节点每页可以存储的数据行会少很多（通常索引相比于整行数据的大小小很多），这样整体树的高度相对就较高，最终如果查询的数据是落在了叶子节点，那么会导致I/O次数过多，不稳定。
- B树叶子节点没有用指针关联，若范围查找，找到第一个数据所在页后，若还需要查找其他数据，需要重新从根节点开始进行查找，效率不高。
B+树
- 非叶子节点只存储索引（冗余索引）
- 叶子节点存储索引和数据
- 叶子节点使用双向指针相互连接形成一个双向链表方便范围查找
总结
由于B+树非叶子节点只存储了索引，这样大大提高了每个非叶子节点可以存储的数据行数量，保证了树的高度可控。同时叶子节点使用双向指针连接形成链表，在执行范围查询，排序等操作时避免了重复从根节点开始查找数据。所以InnoDb最终选择了B+树作为索引的数据结构。
扩展阅读
一个用自增整数(Int)作为主键的树高为3的B+树可以存储多少行数据。
Int需要4字节存储空间, InndoDb索引对应的指针大小为6字节，假设每行数据大小为1KB(在大多数场景中，mysql数据行不会超过1KB大小)，参考上面的B+树图
第一层：根节点 - (16 * 1024) / (4 + 6) = 1638.4
第二层：非叶子节点 - (16 * 1024) / (4 + 6) = 1638.4
第三层：叶子节点 - (16 * 1024) / 1024 = 16
总共可以存储的数量是: 1638 * 1638 * 16 = 42928704
一共可以存储4000多万数据，所以大家明白InnoDb最终为什么选择使用B+树作为索引的数据结构了吧。
Hash
特点
- 只能满足 “=”、“IN” 查询，大多数时候执行此类查询时比B+树高效
- 无序，不支持范围查询
- 存在hash冲突问题，底层使用数组+链表（红黑树）来解决
物理存储角度
聚簇索引（主键索引）
- 每张innodb引擎表只有一个聚簇索引，即主键索引
- 聚簇索引的叶子节点存储了整行的完整数据
- 建议主动给每张表建一个主键，并且最好使用自增的整数，原因如下
- 减少mysql的负担，不要让mysql来计算应该用哪列做主键或自己维护一个隐藏的主键列。
- 考虑查询时的比较效率、大小、存储空间、页分裂树旋转等因素建议使用自增整数
非聚簇索引（二级索引）
- 相比于聚簇索引，非聚簇索引每张表可以建多个
- 非聚簇索引的叶子节点存储的是索引值和主键值
联合索引
思考：如何选择联合索引的顺序
- 最左前缀原则
- 区分度
- 范围查询
- 排序条件
- 尽量通过联合索引完成覆盖索引查询操作
系列文章
上一篇：【Mysql系列文章(一)】Mysql的整体架构及SQL的执行过程
下一篇：【Mysql系列文章(三)】Explain详解