数据库 - MySQL索引原理

本篇从以下几个方面解说数据库索引的知识点：MySQL索引是什么、MySQL索引底层数据结构与算法、MySQL索引最左前缀原理。本文是面试必问的知识点，需重点关注哦~

# 1.1 概述

• 索引是帮助MySQL高效获取数据的排好序的数据结构
• 索引存储在文件里
• 索引结构：BTREE

# 1.2 磁盘存取原理

• 磁盘寻道，时间(速度慢，费时)
• 数据读取，旋转时间(速度较快)

# 1.3 数据结构 B-Tree

• 度(Degree)-节点的数据存储个数
• 叶节点具有相同的深度
• 叶节点的指针为空
• 节点中的数据key从左到右递增排列

# 1.4 MySQL索引数据结构 B+Tree

# 1.4.1 B+Tree的特点

• 非叶子节点不存储data，只存储key，可以增大度
• 叶子节点不存储指针
• 顺序访问指针，提高区间访问的性能

# 1.4.2 B+Tree索引的性能分析

• 一般使用磁盘I/O次数评价索引结构的优劣
• 预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存
• 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用
• B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O
• B+Tree的度d一般会超过100，因此树的深度h会非常小(一般为3到5之间)

# 1.5 MySQL的主流引擎的索引实现（MyISAM 和 InnoDB）

# 1.5.1 MyISAM索引实现(非聚集)

MyISAM索引文件和数据文件是分离的

# 1.5.2 InnoDB索引实现(聚集)

• 数据文件本身就是索引文件
• 表数据文件本身就是按B+Tree组织的一个索引结构文件
• 聚集索引-叶节点包含了完整的数据记录
• 为什么InnoDB表必须有主键，并且推荐使用整型的自增主键？（非主键索引的叶子节点存储的是主键值；自增主键便于新增以及查找）
• 为什么非主键索引结构叶子节点存储的是主键值？(数据一致性和节省存储空间)

# 1.6 联合索引的底层存储结构长什么样

联合索引的比较遵循『索引最左前缀原理』，即依次比较主键，直到可以比较出结果。