MySQL之 B-Tree / B+Tree 索引

mysql

1. 特点

MySQL 的 InnoDB 存储引擎下，使用的索引算法是 B+Tree，在 B-Tree 的基础上，增加了：在叶子节点的兄弟节点之间增加了指针，方便范围遍历。特点有：

• B-Tree 中，数据都是有序的，且每个叶子节点到根节点的距离都一样。
• B-Tree 中，非叶子节点 存储了：
  • 其 下层节点保存的值的 上限 和 下限。即：如果要查找的值不在这个「上下限范围」之内，就不需要沿着这个节点往下查找了。
  • 其 下层节点的指针，用于：向下遍历，进一步缩小 上下限范围，寻找 叶子节点。
• B-Tree 中，叶子节点 中存储了 真实数据的位置（指针）。
• B-Tree 的深度和表的大小正相关。即：V = m^(n-1) V 为容量，m 是叉数，n 是深度。

2. 【可以】使用 B-Tree / B+Tree 索引的查询

以复合索引 index_fname_sname_birthday(first_name, second_name, birthday) 为例：

• 全字段、顺序、等值匹配。如：
  • where first_name="fff" and second_name="sss" and birthday="2020-01-01" and xxx=1，索引包含的三个字段，依次作为查询条件，的等值查询，是能够使用 index_fname_sname_birthday 的（全部字段）。
• 字段顺序、左前缀匹配。如：
  • where first_name="fff" and xxx=1，只能使用 index_fname_sname_birthday 的第一个字段。
  • where first_name="fff" and second_name="sss" and xxx=1，只能使用 index_fname_sname_birthday 的前两个字段。
• 顺序、左前缀 前提下，列前缀匹配。如：
  • where first_name like "f%"，能使用 index_fname_sname_birthday 的第一个字段。
  • where first_name="fff" and second_name like "s%"，能使用 index_fname_sname_birthday 的前两个字段。
  • where first_name="fff" and second_name like "%s%"，则值能使用 index_fname_sname_birthday 的第一个字段。
• 顺序、左前缀 前提下，列范围匹配。如：
  • where first_name > "aaa" and first_name < "fff"，能使用 index_fname_sname_birthday 的第一个字段。
• 顺序、左前缀 前提下，等值前列、范围后列匹配。如：
  • where first_name = "aaa" and second_name < "sss"，能使用 index_fname_sname_birthday 的前两个字段。
  • where first_name > "aaa" and second_name = "sss" and birthday>"2020-01-01"，能使用 index_fname_sname_birthday 索引。

3. 【不可以】使用 B-Tree / B+Tree 索引的查询

以复合索引 index_fname_sname_birthday(first_name, second_name, birthday) 为例：

• 不遵循 索引字段顺序 的查询。如：
  • where xxx=1 and first_name="fff" and second_name="sss" 则不能使用 index_fname_sname_birthday 索引。
  • where first_name="fff" and xxx=1 and second_name="sss"，只能使用 index_fname_sname_birthday 的第一个字段。
• 不遵循 列前缀 的查询。如：
  • where first_name like "%f%"，则不能使用 index_fname_sname_birthday 索引。
• 顺序、左前缀 前提下，前面字段的范围查询，将导致后面的字段不能使用索引。如：
  • where first_name > "aaa" and second_name < "sss"，则只能使用 index_fname_sname_birthday 的第一个字段。
  • where first_name = "aaa" and second_name > "sss" and birthday = "2020-01-01"，则只能使用 index_fname_sname_birthday 的前两个字段。

4. B-Tree / B+Tree 索引的字段顺序

通过上述各种查询语句对复合索引 index_fname_sname_birthday(first_name, second_name, birthday) 的使用情况分析可以得到：在 B+Tree 的复合索引中，字段顺序 将影响复合索引的效率和性能。

• 一个经验法则是：在数据均匀分布 时，将 选择性高的字段 放到前面
  • 一个字段的选择性：
    • 所有值和不同值的数量比例：select count(1) / count(distinct field) from table
  • 以字段 a,b,c 的符合索引来说，假设 a,b,c 的选择性分别是 100, 50, 20，假设表总量 1000 万，查询条件 a=1 and b=2 and c=3：
    • index(a,b,c) 时，a=1 锁定了 1000 万中的 10 万，b=2 锁定了 10 万中的 2000，c=3 锁定了 2000 中的 100 条
    • index(c,b,a) 是，c=3 锁定了 1000 万中的 50 万，b=2 锁定了 50 万中的 10000，a=1 锁定了 10000 中的 100 条
  • 将选择性高的字段放到前面，在查询按照 顺序、左前缀 原则使用索引中的部分字段时，能够得到一个更好的「综合结果」
• 数据不均匀分布时的一个建议：
  • 假设表总行数 1000 万，x 字段选择读 1000，即 x 字段有 10000 个不同值。但假设 x=2 时，有 900 万条数据。
  • 此时，虽然 x 字段的选择读很高，但由于 x 值的不均匀分布，可能导致偶尔的 x=2 的查询把整个系统拖垮。
  • 一个建议是：对这种异常值在程序进行特殊处理，禁止对这个特殊值进行查询。

5. 索引的 三星评价

三星评价 是评价一个索引是否适合一个查询的一种评价方式，以

• index_fname_sname_birthday(first_name, second_name, birthday)
• select first_name, second_name, birthday, gender from user where first_name="三" and second_name="李" and birthday="2020-01-01" order by age

为例：

• 【减少行数据的磁盘IO操作次数】如果索引将查询所需的数据放到了一起，获得一星。
  • 索引中的数据，本身就是有序的，有序就意味着在一起。
  • 索引是否将查询需要的数据放在了一起，其实也就是说：
    • 查询是否用到了索引？
    • 用到了几个字段？
    • 可以理解：查询用到索引的字段越多，这个索引就越是把查询需要的数据放在了一起。
  • 对于上述 查找「李三」 的查询，我感觉这点上能拿到 0.5星，而不是 2/3星，因为我猜测：在一起的程序 和 使用到索引的字段个数 不是线性关系。
• 【减少临时表排序】如果索引中的数据顺序和查找的数据顺序一致，获得二星。
  • 我这里将 顺序一致 理解为：顺序一样 或者 顺序相反，因为 反转 的成本不大。
  • 对于上述 查找「李三」 的查询，查找顺序和索引顺序是否一致：
    • 无论索引中的顺序是：按 birthday 升序 还是 按 birthday 降序，或者是 按主键升序 还是 按主键升序降序，都不可能 按 age 升序或者降序 的。
  • 因此在 查询顺序和索引顺序一致 上，查找「李三」 的查询不得星。
• 【不需要进行行数据的磁盘IO操作】如果查询中的字段在完全包含于索引中，即：可以做到覆盖查询，得三星。
  • 上述有说到：B-Tree 中，叶子节点 中存储了 真实数据的位置（指针），等于是找到了磁盘IO的位置
  • 如果索引中的字段，已经完全包含查询的字段，意味着，不再需要进行 行数据的磁盘IO操作
  • 上述 查找「李三」 的查询中，包含 gender 字段，而 gender 字段不在 index_fname_sname_birthday 索引中，无法覆盖查询，因此 能否覆盖查询 上不得星。
• 虽然上述 查找「李三」 的查询在 三星评价 方式里，只得到了 0.5星，但相对于没有 index_fname_sname_birthday 索引时的 全表扫描 大大减少了扫描行数，减少了扫描行数据时的磁盘IO操作。

6. 索引使用中的一些 坑

• 将字段作为表达式一部分或函数参数时，将不能再使用索引。如：
  • index(age, gender), select ... from user where age+1 = 20;
  • index(order_id, created_at), select ... from order where DATE(CURRENT_DATE) - DATE(created_at) <= 10;
• 非常长的字符串使得索引很慢。如：
  • index(name) 很慢时，通过上述 字段选择性 方式，选择一个合适的前缀长度作为索引。即：select count(1)/count(distinct left(name, 3)) as name3, count(1)/count(distinct left(name, 4)) as name4 ... from ...;
• 太多的 单字段 索引。如：
  • table user, index(name), index(age), index(grade)...
  • 太多的 单字段 索引，会涉及 多个个索引结果的合并和相交，而有些时候 一个多字段的复合索引 可能更合适。
• 有意无意的重复索引。如：
  • index(user_id), unique(user_id), user_id primary key