MySQL索引的数据结构

建立索引的原则

• 最左前缀匹配原则
• 尽量选择重复度小的列
• 索引列不参与计算
• 尽量扩展索引，不要新建索引

索引的数据结构

索引是在MySQL的存储引擎层中实现的，而不是在服务器层实现的。所以每种存储引擎的索引都不一定完全相同。

B+树容量计算

磁盘存储数据最小单元：扇区，512字节
文件系统最小单元：块，4K
InnoDB存储引擎的最小存储单元：页page，一个页的大小是16K，即16*1024=1170字节

假设高度为2的B+树如图：

image.png
每页存放叶子节点的个数
假设一行记录的数据为1k，每页可存放 16k/1k = 16 行数据。例如：page2
每页存放的非叶子节点个数
非叶子节点=键值+指针，假设主键ID为bigint类型，长度为8字节，指针大小在InnoDB源码中设置为6字节， 一个非叶子节点共占14个字节，每页可存放 161024/14 = 1170 个非叶子节点。
每页共存放叶子节点 1170个非叶子节点 * 16个叶子节点 = 18720。例如：page1。
一个高度为3的B+树可以存储 117018720 = 21902400 行数据。
在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

B树与B+树的区别

• B+树只在叶子节点存放数据，非叶子节点充当叶子节点的索引；B树非叶子节点也存放数据。导致存储的指针少，树的高度更高，查询次数增加，性能变低。
• B+树查询效率稳定，数据都在叶子节点上，所有查询都是从根节点走向叶子节点，查找次数相同；B树检索数据时，在非叶子节点和叶子节点上都有可能，越靠近根节点，效率越快。
• B+树支持随机检索和顺序检索；B树适合随机检索，顺序检索比B+树效率低。
• 增删文件时，B+树所有的data都在叶子节点中，效率更高；B树删减节点时需要分裂，中间节点向上等操作。

Hash索引

适合等值查找，不支持区间查找；
不支持模糊查询，数据之间没有关联性；
某个键值大量重复时，会发生hash碰撞，效率变低；