5.索引与算法
2020-11-15 20:19:42 0 举报AI智能生成
登录查看完整内容
mysql索引
作者其他创作
大纲/内容
索引与算法
1. InnoDB存储引擎索引概述
类型
B+树索引
B+树索引并不能找到一个给定键值的具体行
B+树索引能找到的只是所查找数据行所在的页，然后通过数据库把页读到内存中，再在内存中进行查找，最后得到要查找的结果
全文索引
哈希索引
2. 数据结构与算法
二分查找法
二分查找法也称为折半查找法，用来查找一组有序的记录数组中的某一记录。基本思想:将记录按有序化(递增或递减)排列，在查找的过程中采用跳跃式方式查找，即先以有序队列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。
二叉查找树
二叉查找树是一种经典的数据结构，在二叉查找树中，左子树的键值总之小于根的键值，右子树的键值总是大于根的键值。可以通过中序遍历得到键值的排序输出。
想最大性能地构造出一棵二叉树，需要这个二叉树是平衡的。
平衡二叉树
首先必须符合二叉树的定义，其次必须满足任何节点的两个子树的高度最大差是1.
B+树
定义
B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。
B+树的插入操作
B+树的插入必须保证插入后叶子节点中的记录依然排序，为了保持平衡对于新插入的键值可能需要做大量的拆分页操作。因为B+树结构主要用于磁盘，页的拆分意味着磁盘的操作，所以应该在可能的情况下尽量减少页的拆分操作。
B+树的删除操作
B+树使用填充因子来控制树的删除变化，50%是填充因子可设的最小值。B+树的删除操作同样需要保证删除后叶子节点中的记录依然排序，如果删除一条记录后，填充因子小于50%，需要做索引页的合并操作。
3. B+树索引
分类
聚集索引
叶子节点存放的是一行完整的记录
辅助索引
叶子节点只存键值
B+树索引的管理
ALTER TABLE
CREATE/DROP INDEX
B+树索引的使用
联合索引
对表上的多个列进行索引
覆盖索引
从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。
使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作
索引提示
显式地告诉优化器使用哪个索引
方式
USE INDEX
告诉优化器可以选择该索引，实际上优化器会再根据自己的判断选择
FORCE INDEX
指定使用指定索引
Multi-Range Read优化
目的
为了减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，这对IO-bound类型的SQL查询语句可带来性能极大的提升
优点
MRR使数据访问变得较为顺序。在查询辅助索引时，首先根据得到的查询结果，根据主键进行排序，并按照主键排序的顺序进行书签查找
减少缓冲池页被替换的次数
批量处理对键值的查询操作
工作方式
将查询得到的辅助索引键值存放与一个缓存中，这时缓存中的数据是根据辅助索引键值排序的
将缓存中的键值根据RowID进行过排序
根据RawID的排序顺序来访问实际的数据文件
Index Condition Pushdown优化
在取出索引的同时，判断是否可以进行WHERE条件的过滤，也就是将WHERE的部分过滤操作放在了引擎层
4.全文检索
概述
倒排索引
InnoDB全文检索
全文检索
0 条评论
回复 删除
下一页
