MySQL 性能优化——B+Tree 索引

什么是索引

索引是为了实现mysql高性能查询的数据结构。

为了快速查询数据,MySql在查询算法上进行了许多优化。但是就如二叉树查找算法只能应用于二叉树数据结构一样,需要有满足这种查找算法的数据结构,而数据本身的结构可能并不能满足查找算法所需要的数据结构,所以MySql在数据之外维护了一个能应用于高效的查找算法的数据结构,这种数据结构,就是索引。
接下来将介绍使用最多的索引类型——B-Tree索引

B-Tree

B-Tree索引通常用的是B-Tree的变种B+Tree数据结构

B-Tree的节点是一个二元数组[key,data],key是记录的键,data是键对应的数据,每个节点的每个key左右各有一个指针,非叶子节点的指针分别指向下一层的节点,叶子节点的指针为null,如下图:
3151600-7f2ab93d1be2e566.png
要查找值的时候,会先从根节点开始查找,根节点的每个key有左右两个指针,可以通过这两个指针访问下一层节点。每次查找都会将查找值与key值进行比较,根据比较结果找到合适的指针进入下一层节点,最终,如此重复,最终找到对应的值或者值不存在

B+Tree

B+Tree节点是B-Tree的变种,相对于B-Tree而言B+Tree有如下不同:

在每个非叶子节点只会存储key而不会存储data,data将统一存储到叶子节点中,叶子节点页不需存储指针,但是增加了指向相邻叶子节点的指针

如下图
2015-07-07_559b77f1e1377.png

可以使用B-Tree(B+Tree)索引的查询类型

1.全键值查找,如whre key=val的查询条件
2.键值范围查找,如where key>0此类型的范围查找
3.键前缀查找(只适合于最左前缀查找),如where key like 'abc%'有效,where key like '%abc'where key like '%abc%'等方式都无效

B-Tree(B+Tree)索引的限制

1.只能按照最左列开始查找,否则无法使用
2.不能跳过索引中的列,例如有key(a,b,c),不能直接跳过a列使用b列索引,所以在创建索引的时候,顺序也很重要
3.如果查询中有一个列使用了范围查询,则右边所有列都不能使用索引

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 6
键前缀查找(只适合于最左前缀查找),如where key like '%abc'有效···!

这个没问题吗?

5年前 评论

@子兴的期盼 多谢指出,这个查询并不是最左前缀,应该是无法使用索引

5年前 评论
lmaster

@GameTo @子兴的期盼 MySQL like 问题比较复杂,建议你自己测试下,推荐看下 这里

2019-03-25 15:35
发现推荐的连接里面的给出的有问题,我自己在数据库跑了一下

EXPLAIN SELECT * FROM test WHERE uname LIKE 'j%';

图片

EXPLAIN SELECT * FROM test WHERE uname LIKE '%j';

图片
我的mysql version :5.5.53

5年前 评论

@lmaster 你好,我看了您放的文章。
先说结论:关于文章中测试得出的非最左前缀也会使用索引的情况是因为覆盖索引。
索引覆盖是当你要查询的列,在索引中都已经存在时,就不会回表查询,而是直接从索引查询。
id和uname都在索引中存在,满足索引覆盖的条件,所以mysql会使用索引而不会回表查询,但是因为uname的条件不是最左前缀,这条语句虽然使用了索引,却无法享受B+TREE数据结构所带来查询算法上的优化,不过也会比回表查询的语句快很多,这是由索引的存储位置决定的。

5年前 评论
lmaster

@GameTo 我发现那个连接里面的东西有问题,自己在数据库跑了一次

id和uname都在索引中存在,满足索引覆盖的条件,所以mysql会使用索引而不会回表查询,但是因为uname的条件不是最左前缀,这条语句虽然使用了索引,却无法享受B+TREE数据结构所带来查询算法上的优化,不过也会比回表查询的语句快很多,这是由索引的存储位置决定的。

这句不太理解,我去研究研究,能否提供一些资料

5年前 评论

@lmaster 《高性能MySQL》索引章节和查询优化章节有详细介绍

4年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!