索引是为了实现 mysql 高性能查询的数据结构。
为了快速查询数据,MySql 在查询算法上进行了许多优化。但是就如二叉树查找算法
只能应用于二叉树
数据结构一样,需要有满足这种查找算法的数据结构,而数据本身的结构可能并不能满足查找算法所需要的数据结构,所以 MySql 在数据之外维护了一个能应用于高效的查找算法的数据结构,这种数据结构,就是索引。
接下来将介绍使用最多的索引类型 ——B-Tree 索引
B-Tree 索引通常用的是 B-Tree 的变种 B+Tree 数据结构
B-Tree 的节点是一个二元数组 [key,data]
,key 是记录的键,data 是键对应的数据,每个节点的每个 key 左右各有一个指针,非叶子节点的指针分别指向下一层的节点,叶子节点的指针为 null,如下图:
要查找值的时候,会先从根节点开始查找,根节点的每个 key 有左右两个指针,可以通过这两个指针访问下一层节点。每次查找都会将查找值与 key 值进行比较,根据比较结果找到合适的指针进入下一层节点,最终,如此重复,最终找到对应的值或者值不存在
B+Tree 节点是 B-Tree 的变种,相对于 B-Tree 而言 B+Tree 有如下不同:
在每个非叶子节点只会存储 key 而不会存储 data,data 将统一存储到叶子节点中,叶子节点页不需存储指针,但是增加了指向相邻叶子节点的指针
如下图
1. 全键值查找,如 whre key=val
的查询条件
2. 键值范围查找,如 where key>0
此类型的范围查找
3. 键前缀查找(只适合于最左前缀查找),如 where key like 'abc%'
有效,where key like '%abc'
或 where key like '%abc%'
等方式都无效
1. 只能按照最左列开始查找,否则无法使用 2. 不能跳过索引中的列,例如有 key (a,b,c),不能直接跳过 a 列使用 b 列索引,所以在创建索引的时候,顺序也很重要 3. 如果查询中有一个列使用了范围查询,则右边所有列都不能使用索引