MySQL 性能优化——B+Tree 索引
MySQL 性能优化——B+Tree 索引
什么是索引
索引是为了实现 mysql 高性能查询的数据结构。
为了快速查询数据，MySql 在查询算法上进行了许多优化。但是就如二叉树查找算法只能应用于二叉树数据结构一样，需要有满足这种查找算法的数据结构，而数据本身的结构可能并不能满足查找算法所需要的数据结构，所以 MySql 在数据之外维护了一个能应用于高效的查找算法的数据结构，这种数据结构，就是索引。
接下来将介绍使用最多的索引类型 ——B-Tree 索引
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 而言 B+Tree 有如下不同：
在每个非叶子节点只会存储 key 而不会存储 data，data 将统一存储到叶子节点中，叶子节点页不需存储指针，但是增加了指向相邻叶子节点的指针
如下图
可以使用 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. 如果查询中有一个列使用了范围查询，则右边所有列都不能使用索引