引言
我为什么要写或者基于啥目的要写这篇文章? -- 为了面试备忘,在面试中吃了八股文太多的亏了
B树与B+树的区别
B树叫多路平衡搜索树,每个节点可以存储多个数据,存储数据的个数由B树的度决定。
B+树是B树的一种变形,B+树元素自底向上插入,这与二叉树恰好相反,所有的数据都存储在叶子节点上,非叶子节点的数据都是叶子节点数据的冗余。叶子节点之间的数据通过指针连接。
绘图工具: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
为什么不用B树而用B+树
-
B树不适合范围查找 比如我要查找小于6的数据,则先找到6的节点,然后需要遍历一遍6节点(索引)的左子树,不遍历的话,就拿不到小于6的这些数据了,也就说索引失效了,所以说不适合范围查找。
-
页大小和稳定性的考量 B树的节点除了存储索引之外,还存储了数据本身,占用空间较大,但是磁盘的页大小是有限的(16KB左右),因此,存储同样大小的数据,BTree显得比较高(相对B+Tree),稳定性弱一些。
高度为N的B+树可以存多少条数据
树高度等于2时(2阶),如果记录大小为1KB,以INT类型为索引:
页编号(索引页)大小:page_size(16kb) / (index_type_size(4byte)+page_dir_pointer(6byte)) = 16kb/10b .= 1638
意味着2阶B+树可以存储约1638个页,每页数量(数据页)为 16kb/1kb = 16,得2阶B+树可以存数据 = 16*1638 = 26208
高度等于3时(3阶)时:
一级页编号大小 1638,二级页编号大小 = 1638^2, 得3阶B+树可以存数据 = 16*1638^2 = 42928704
幻读与不可重复读
我一直以来都把幻读理解为了不可重复读。此话怎讲?
以前的观念:
幻读是 事务A 执行两次 select 操作得到不同的数据集,即 select 1 得到 10 条记录,select 2 得到 15 条记录。
这其实并不是幻读,既然第一次和第二次读取的不一致,那不还是不可重复读吗,所以这是不可重复读的一种。
现在的观念:
幻读,并不是说两次读取获取的结果集不同,幻读侧重的方面是某一次的 select 操作得到的结果所表征的数据状态无法支撑后续的业务操作。更为具体一些:select 某记录是否存在,不存在,准备插入此记录,但执行 insert 时发现此记录已存在,无法插入,此时就发生了幻读。
引用自: 一文详解脏读、不可重复读、幻读
explain 温习
在复习索引之前,有必要再温习记录一下 explain
这个SQL查询优化器能给我们哪些索引优化的提示。
诸如在某次执行后的结果集如下:
id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
---|---|---|---|---|---|---|---|---|---|
1 | SIMPLE | course | range | PRIMARY | PRIMARY | 4 | 9 | Using where |
id : select查询的序列号,包含一组数字,表示查询中执行select子句或操作表的顺序 table :正在访问哪个表 通过 id 与 table 字段可以得知子查询何连表查询等的查表顺序。 select_type : 查询类型。
- SIMPLE 简单查询。
- PRIMARY 当存在子查询时,最外面的查询被标记为主查询。
- SUBQUERY 子查询。
- UNION 当一个查询在UNION关键字之后就会出现UNION。
- UNION RESULT 连接几个表查询后的结果
type :访问的类型。
NULL: 在执行阶段用不着再访问表或索引
system:查系统表
const:通过索引一次就找到了(直接按主键或唯一键读取)
eq_ref:主键或唯一键联合查询
ref:非唯一性索引扫描
ref_or_null:类似ref,但是可以搜索值为
NULL
的行 index_merge:查询使用了两个以上的索引,最后取交集或者并集 range:索引范围查询 index:index
只遍历索引树,通常比All
快。因为,索引文件通常比数据文件小,也就是虽然all
和index
都是读全表,但index
是从索引中读取的,而all
是从硬盘读的。 ALL:如果一个查询的type
是All
,并且表的数据量很大,那么请解决它!!!
possible_keys :显示可能应用在这张表中的索引,一个或多个,但不一定实际使用到 key : 实际使用到的索引,如果为NULL,则没有使用索引 key_len :表示索引中使用的字节数,可通过该列计算查询中使用的索引的长度 ref:显示索引的哪一列被使用了,如果可能的话,是一个常数,哪些列或常量被用于查找索引列上的值 rows: 根据表统计信息及索引选用情况,大致估算出找到所需的记录所需读取的行数 Extra:包含不适合在其它列中显示但十分重要的额外信息
- Using filesort 对没有建立索引的字段进行排序
- Using tempporary对MySQL查询结果进行排序时,使用了临时表,这样的查询效率是比外部排序更低的,常见于
order by
和group by
。 - Using index表示使用了索引
- Using where可能全表扫描;可能回表读数据 然后过滤;
- Using Index Condition先条件过滤索引,过滤完索引后找到所有符合索引条件的数据行,随后用 WHERE 子句中的其他条件去过滤这些数据行;
innodb是如何支持查询时走索引的
innodb 数据的数据页间通过双向链表连接,数据页内数据通过单向链表连接,类似 between and
> <
都是利用了数据页间的双向链表完成的。
最左前缀原则下的索引问题
对于联合索引,通过最左前缀原则指导搜索。例如 a为主键, bcd组合成联合索引,那么对于以下情况:
select * from user where b = 1 and c = 1 and d = 1; -- 走索引
select * from user where b = 1 and c = 1; -- 走索引
select * from user where b = 1 and d = 1; -- 不走索引
select * from user where c = 1 and d = 1; -- 不走索引
order by 为何导致索引失效
并不是说使用了 order by
就一定不走索引。 不使用 order by
时,结果集按照默认升序进行结果输出,当 order by
介入并不按照给定索引进行排序,就会导致额外文件排序。所谓的索引失效主要是说额外的Using filesort,因为走索引时,且order by按照索引顺序进行,并利用覆盖索引方式进行查找,是不会带来 Using filesort
的开销的。
必定导致 Using filesort
的 order by
情况有如下
-- 依然是 a 为主键索引 bcd为联合索引
explain SELECT b,c,d from course order by b, c, d; //Using index
-- 未按照最佳左前缀原则进行 order by
explain SELECT b,c,d from course order by c, d; // Using index; Using filesort
-- where 中使用最佳左前缀为条件
explain SELECT b,c,d from course where b = 1 order by c, d; // Using where; Using index
explain SELECT b,c,d from course where c = 2 order by b, d; //
-- order by 中同时包含 asc, desc 一定会 using filesort
explain SELECT b,c,d from course where b = 1 order by c asc, d desc; // Using where; Using index; Using filesort
小结一下失效原因:
-
字段排序不一致
-
最佳左前缀丢失
-
字段不是索引的一部分