索引和算法
索引概述
- B+索引
- 全文索引
- 哈希索引: mysql支持的hash索引是自适应的,不能认为干预是否在一张表中生成
数据结构和算法
二分查找法
将记录按有序排列,在查找过程中采用跳跃式的方式查找,即先以有序数列的中点位置为比较对象
其中找到页后,在查找具体行记录时,在pagedirectory中使用二分查找
二叉查找树和平衡二叉树
二叉查找树
二叉查找树中,左子树的键值总小于根的键值,右子树的键值总大于根的键值
平衡二叉树
首先符合二叉查找树的定义,其次满足任何节点的两个子树的高度最大差为1
B+树
为磁盘或其他直接存取辅助设备设计的一种平衡查找树,在B+树种,所有记录节点都是按照键值的大小放在同一层的叶子节点,有哥哥叶子节点进行连接
聚集索引
按照每张表主键构造一颗B+树,同时叶子节点存放的即为整张表的行记录数据,每张表只能拥有一个聚集索引,聚集索引的存储并不是物理连续的,而是逻辑连续的,一是每个页通过双向链表连接,二是每个页中的记录也通过双向链表连接
辅助索引
即非聚集索引,叶子节点并不包含行记录的全部数据,叶子节点除了包含键值外,还包含一个书签,告诉innodb在哪里找到与索引相对应的行的数据
1.png
先查找辅助索引,在根据辅助索引的主键id,查找聚集索引
B+树索引的修改
- Fast Index Creation
对数据表增加S锁,不影响读影响写入 - Online scheme Change
创建临时表,将原有数据导入,然后同步这段时间写入的数据,最后rename - Online DDl
B+树索引的使用
联合索引
对表上多个列进行索引,并且按照索引的顺序在B+树上进行排序,并且在orderby时如果按照索引的顺序排序,可以避免filesort覆盖索引
从辅助索引中就可以得到查询的记录,不需要查询聚集索引中的记录Multi-Range Read优化
- MRR是数据访问变得较为顺序,在查询辅助索引时,结果按照主键进行排序,在顺序查找聚集索引
- 减少缓冲池中页被替换的次数
- 批量处理对键值的查询操作
