深入理解Mysql索引底层数据结构和算法

索引是什么？

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

常见的数据结构

• 二叉树
• 红黑树
• Hash表
• B Tree
• B+ Tree(B Tree的变种)

二叉树

缺点：对于自增的序列， 其二叉树中任何节点都没有左子树， 是一个单边增长的结构。作为索引数据结构的话，此时性能很差。

红黑树

缺点： 高度不可控，且随着数据量的增加，高度越来越深。

Hash表

缺点：

• Hash表是根据key值求hash值定位到具体位置， 只能满足sql的=、in 的操作，无法满足范围查询
• hash冲突问题

B Tree

1、分析B Tree的数据表可以存储多大的数据量：

        一个节点对应一个数据页（Mysql磁盘页大小默认16KB）, 假设主键是bigint类型占8字节，指针6字节， 一条数据1KB，B+ Tree 深度 = 3

每个节点可以存储的索引节点 16KB / （1KB + 8B + 6B） = 16

则可以存储的数据记录数=16 * 16 * 16 = 4096

2、分析磁盘IO次数

        因为非叶子节点也存储的data，磁盘IO次数不可控

B+ Tree

1、分析B+ Tree的数据表可以存储多大的数据量：

        一个节点对应一个数据页（Mysql磁盘页大小默认16KB）, 假设主键是bigint类型占8字节，指针6字节， 一条数据1KB，B+ Tree 深度 = 3

一个非叶子节点可以存储的索引节点 16KB / （8+6） = 1170 个

一个叶子节点可以存储的data个数 16KB / （1KB + 8字节）  = 16 个

则可以存储的数据记录数=1170 * 1170 * 16 = 2190W

2、分析磁盘IO次数

        有的存储引擎根节点常驻内存， 对应深度=3的B+ Tree, 主键查询时IO次数=2， 非主键查询时IO次数=3

存储引擎的数据结构

存储引擎：用于存储数据，提供读写接口。

存储引擎作用的是数据表，而不是数据库。

MyISAM

MyISAM的索引文件和数据文件是分离的（非聚集）

MyISAM数据表对应的文件：

• .frm  表的结构信息
• .MYD数据信息
• .MYI索引信息

InnoDB

InnoDB数据表对应的文件：

• .frm  表的结构信息
• .ibd数据信息

存储引擎比较

	MyISAM	InnoDB
叶子节点之间	单向指针	双向指针
叶子节点内容	索引+指向data的指针（非聚集索引）	1.主键索引：索引+data（聚集索引） 2. 非主键索引：索引+指向data的指针（非聚集索引）

结合存储引擎的数据结构，回答几个索引问题：

1. 为什么建议InnoDB表必须有主键？

        mysql在存储数据时是按照主键来存储的（聚集索引），若没有创建主键，mysql会自己选择一列作为主键：

• 选择一列没有重复数据的列
• 如果这种列不存在，mysql创建一个隐藏列作为主键列

        所以我们可以帮msyql做的事情就自己做了，而不是交给mysql去做。

2. 为什么建议InnoDB表主键建议是整型？

• 整型和字符串相比， 更容易比较大小
• 整型占用空间大小更小，存储时节省固态硬盘

3. 为什么建议InnoDB表主键建议是自增？

        B+树种不断增加元素，如果一个节点的元素数量超过限制，要么新增一个节点，要么一个节点分裂。如果是自增， 会导致B+树新增一个节点而不是节点分裂，从B+树的构建过程来看，新增一个节点肯定比节点分裂效率更高。

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

• 数据一致性
• 节省存储空间

联合索引

索引最左前缀原理