【性能调优】Mysql索引数据结构详解
1.概述
索引是帮助MySQL高效获取数据的排好序
的数据结构
。
索引存储在文件里
常见的索引结构:
- 二叉树
- 红黑树
- HASH
- BTREE
数据结构存储演示
MySQL底层采用的是BTREE。因为一般当数据量过大时,红黑树的深度过大,高度不可控。而哈希存在的问题是只便于精确定位某一行,当查询范围值的时候不便。B-Tree则一个节点可存储多个索引。
磁盘存取原理
- 寻道时间(速度慢,费时)
- 旋转时间(速度较快)
2.B-Tree
B-Tree
- 度(Degree)-节点的数据存储个数
- 叶节点具有相同的深度
- 叶节点的指针为空
- 节点中的数据key从左到右递增排列
问题
:如果h为1,全放在一个节点,度无限大,这样会有什么问题?
磁盘IO寻道一次IO取的页,即RAM与硬盘交互只能交互的页有上限,如果度很大的话,那还是要很多次IO才能取出来一个节点的数据。一般一个node的大小为一页
B+Tree(B-Tree变种)
- 非叶子节点不存储data,只存储key,
可以增大度
- 叶子节点不存储指针
- 顺序访问指针,提高区间访问的性能
B+Tree索引的性能分析
一般使用磁盘I/O次数评价索引结构的优劣
- 预读:磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存
- 局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用
- B+Tree节点的大小设为等于
一个页
,每次新建节点直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,就实现了一个节点的载入只需一次I/O - B+Tree的度d一般会超过100,因此h非常小(
一般为3到5之间
)
3.存储引擎
MyISAM索引实现(非聚集
)
MyISAM
索引文件和数据文件是分离的
我们发现,主键索引和非主键索引的存储结构是一样的,所以MyISAM需要维护多套数据结构。
InnoDB索引实现(聚集
)
- 数据文件本身就是索引文件
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
- InnoDB表必须有主键,推荐使用整型的自增主键
- 非主键索引结构叶子节点存储的是主键值(一致性和节省存储空间)
我们发现,InnoDB主键索引与非主键索引结构不一样,虽然也是采用B+Tree,但是非主键索引结构的叶子节点存的是主键。 -
问题
:为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?
B+树连续递增存储,使用整数首先节点比较的时候进行整数比较,另一方面自增主键会自动将节点添加到尾部。 -
问题
:为什么非主键索引结构叶子节点存储的是主键值?
非主键索引存储的叶子结点为主键,节省存储空间,数据一致性。 -
问题
:为什么不推荐uuid作为主键?
进行查找操作的时候比较大小,如果使用uuid作为主键的话,那么会使用ascii比较,性能较低。另一方面在使用uuid插入的时候随机插入,可能会有节点分裂。而使用整数递增索引的话,直接插入尾部。 -
问题
:存储引擎是基于表的还是基于数据库的?
使用Navicat创建表时,我们点击选项发现可以选择引擎,这说明是基于表的,即一个数据库下可有多个不同的引擎。默认为InnoDB。
联合索引存储结构
4.问题
分析以下几条sql的索引使用情况
- SELECT * FROM titles WHERE emp_no=‘10001’ AND title=‘Senior Engineer’ AND from_date=‘1986-06-26’;使用了索引
- SELECT * FROM titles WHERE title=‘Senior Engineer’ ;
- SELECT * FROM titles WHERE emp_no > ‘10001’;
- SELECT * FROM titles WHERE emp_no > ‘10001’ and title=‘Senior Engineer’;
- SELECT * FROM titles WHERE emp_no > ‘10001’ order BY title;