深入理解Mysql索引底层数据结构与算法
索引到底是什么
1、索引是帮助MySQL高效获取数据的排好序的数据结构
2、索引存储在文件里
3、索引结构B树
B树
- B-Tree
- 度(Degree)-节点的数据存储个数
- 叶节点具有相同的深度
- 叶节点的指针为空
- 节点中的数据key从左到右递增排列
········································································
-
B+Tree(B-Tree变种)
-
非叶子节点不存储data,只存储key,可以增大度
-
叶子节点不存储指针
-
顺序访问指针,提高区间访问的性能
````````````````````````````````````````````````````````````````````````````````````````
B+Tree索引的性能分析
1.一般使用磁盘I/O次数评价索引结构的优劣
2.预读:磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存
3.局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用
B+Tree节点的大小设为等于一个页,每次新建节点直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,就实现了一个节点的载入只需一次I/O
4.B+Tree的度d一般会超过100,因此h非常小(一般为3到5之间)
索引实现
MyISAM索引实现(非聚集)
- MyISAM索引文件和数据文件是分离的
InnoDB索引实现(聚集)
- 数据文件本身就是索引文件
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
- 为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?
- 为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)
联合索引的底层存储结构长什么样?