索引是帮助高效获取数据的数据结构,避免全表扫描
mysql为什么用B+TREE作索引?而不是其它树形 结构?比如B树?
尽量少地访问资源是数据库设计的重要原则之一。
B树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节 点中能保存的指针数量变少(有些资料也称为扇出),指针少的情况下要保 存大量数据,只能增加树的高度,导致IO操作变多,查询性能变低;
mysql索引如何实现?
我们先将数据记录按主键进行排序,分别存放在不同的页中(为了便于理解 我们这里一个页中只存放3条记录,实际情况可以存放很多),除了存放数据 的页以外,还有存放键值+指针的页,如图中page number=3的页,该页存放 键值和指向数据页的指针,这样的页由N个键值+指针组成。当然它也是排好 序的。这样的数据组织形式,我们称为索引组织表。
1、InnoDB存储引擎的最小存储单元是页,页可以用于存放数据也可以用于 存放键值+指针,在B+树中叶子节点存放数据,非叶子节点存放键值+指针。
2、索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中, 进而在去数据页中查找到需要的数据;
什么是回表?现在,我们一起来看看这条SQL查询语句的执行流程:
1. 在k索引树上找到k=3的记录,取得 ID = 300;
2. 再到ID索引树查到ID=300对应的R3;
3. 在k索引树取下一个值k=5,取得ID=500;
4. 再回到ID索引树查到ID=500对应的R4;
5. 在k索引树取下一个值k=6,不满足条件,循环结束。
在这个过程中,回到主键索引树搜索的过程,我们称为回表。
可以看到,这个查询过程读了k 索引树的3条记录(步骤1、3和5),回表了两次(步骤2和4)。 在这个例子中,由于查询结果所需要的数据只在主键索引上有,所以不得不回表。
什么是覆盖索引?避免回表过程
如果执行的语句是select ID fromTwhere k between 3 and 5,这时只需要查ID的值,而ID的值 已经在k索引树上了,因此可以直接提供查询结果,不需要回表。也就是说,在这个查询里面, 索引k已经“覆盖了”我们的查询需求,我们称为覆盖索引。
Msql5.6引入的索引下推优化MySQL 5.6 引入的索引下推优化(index condition pushdown), 可以在索引遍历过程中,对索 引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。
无索引下推优化
索引下推优化
每个虚线箭头表示一次回表
为什么删除了表的部分记录,它的索引还在?
alter table T engine=InnoDB
B+树在线模拟
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html