# B-tree 索引

{% hint style="success" %} <mark style="color:blue;">**B-tree 通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。**</mark>

B-tree 索引能够加快数据访问的速度，这是因为**有了索引，在查询某些条件的数据时，存储引擎不再需要进行全表扫描。**&#x800C;是从索引的根节点开始进行搜索，根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么找到对应的值，要么该记录不存在。

叶子节点比较特殊，它们的指针指向的是被索引的数据，而不是其他的节点页。

<mark style="color:blue;">**B-tree 是按照索引列中的数据大小顺序存储的，所以很适合按照范围来查询。**</mark><mark style="color:orange;">**索引对多个值进行排序的依据是 CREATE TABLE 语句中定义索引时列的顺序。**</mark>
{% endhint %}

可以利用 B-Tree 索引进行<mark style="color:blue;">**全关键字**</mark>、<mark style="color:blue;">**关键字范围**</mark>和<mark style="color:blue;">**关键字前缀**</mark>查询。

## MySQL 中能够使用索引的典型场景

1. <mark style="color:blue;">**匹配全值（Match the full value）**</mark>，对索引中所有列都指定具体值，即是对索引中的所有列都有等值匹配的条件。
2. <mark style="color:blue;">**匹配值的范围查询（Match a range of values）**</mark>，对索引的值能够进行范围查找。
3. <mark style="color:red;">**匹配最左前缀（Match a leftmost prefix）**</mark>，仅仅使用索引中的最左边列进行查找，比如在 col1 + col2 + col3 字段上的联合索引能够被包含 col1、（col1 + col2）、（col1 + col2 + col3）的等值查询利用到，可是不能够被 col2、（col2 + col3）的等值查询利用到。
4. [<mark style="color:blue;">**覆盖索引**</mark>](https://bohans.gitbook.io/ji-chu/mysql/sql-you-hua/suo-yin/fu-gai-suo-yin)查询，仅仅对索引进行查询（Index only query），当查询的列都在索引的字段中时，查询的效率更高。
5. <mark style="color:blue;">**匹配列前缀（Match a column prefix）**</mark>，仅仅使用索引中的第一列，并且只包含索引第一列的开头一部分进行查找。注意：可以结合最左前缀规则。

   ```sql
   SELECT title
   FROM film_text
   WHERE title LIKE 'AFRICAN%'
   ```
6. 能够实现索引匹配部分精确而其他部分进行范围匹配（Match one part exactly and match a range on another part）。

   ```sql
   SELECT inventory_id
   FROM rental
   WHERE rental_date = '2006-02-14 15:16:03'
     AND customer_id >= 300
     AND customer_id <= 400;
   ```
7. 如果列名是索引，那么使用 **column\_name IS NULL** 会使用索引（区别于 Oracle）。
8. 因为索引树中的节点是有序的，所以除了按值查找，索引还可以用于查询中的 <mark style="color:blue;">**ORDER BY**</mark> 操作（按顺序查找）。<mark style="color:orange;">**一般来说，如果 B-tree 可以按照某种方式查找到值，那么也可以按照这种方式去排序。**</mark>所以，如果 ORDER BY 子句满足前面列出的几种查询类型，则这个索引也可以用于这类排序场景。
9. MySQL 5.6 引入了 <mark style="color:blue;">**Index Condition Pushdown（ICP）**</mark>的特性，进一步优化了查询。Pushdown 表示操作下放，某些情况下的条件过滤操作下放到存储引擎。\
   例如，查询租赁表 rental 中租赁时间 rental\_date 在某一指定时间点且客户编号 customer\_id 在指定范围内的数据：

   ```sql
   EXPLAIN
   SELECT *
   FROM rental
   WHERE rental_date = '2006-02-14 15:16:03'
     AND customer_id >= 300
     AND customer_id <= 400 \G;
   ```

   * **MySQL 5.5/5.1** 版本的执行计划显示：优化器首先使用复合索引 idx\_rental\_date 的首字段rental\_date 过滤出符合条件 rental\_date='2006-02-14 15:16:03' 的记录（执行计划中 key 字段值显示为 idx\_rental\_date），然后根据复合索引 idx\_rental\_date 回表获取记录后，**最终根据条件  customer\_id >= 300 and customer\_id <= 300 来过滤出最后的查询结果**（执行计划中 Extra 字段值显示为 Using where）。
   * 在 MySQL 5.6 上做同样的案例，能够发现 Explain 执行计划的 Extra 部分从 Using where 变成了 <mark style="color:blue;">**Using index condition**</mark> 的提示：

     ```sql
     *************************** 1. row ***************************
                id: 1
       select_type: SIMPLE
             table: rental
        partitions: NULL
              type: ref
     possible_keys: rental_date,idx_fk_customer_id
               key: rental_date
           key_len: 5
               ref: const
              rows: 182
          filtered: 16.85
             Extra: Using index condition
     ```

     \ <mark style="color:blue;">**Using index condition**</mark> 就表示 MySQL 使用了 <mark style="color:blue;">**ICP**</mark> 来进一步优化查询，**在检索的时候，把条件 customer\_id 的过滤操作下推到存储引擎层来完成，这样能够降低不必要的 IO 访问。**

## 存在索引但不能使用索引的典型场景

* <mark style="color:blue;">**以 % 开头的 LIKE 查询**</mark>不能够利用 B-Tree 索引，执行计划中 key 的值为 NULL 表示没有使用索引。

  ```sql
  EXPLAIN
  SELECT *
  FROM actor
  WHERE last_name LIKE '%NI% \G;
  ```

  ```
  *************************** 1. row ***************************
             id: 1
    select_type: SIMPLE
          table: actor
     partitions: NULL
           type: ALL
  possible_keys: NULL
            key: NULL
        key_len: NULL
            ref: NULL
           rows: 200
       filtered: 11.11
          Extra: Using where
  ```

  \
  因为 B-Tree 索引的结构，所以以 % 开头的查询很自然就没法利用索引了，一般都推荐使用全文索引（Fulltext）来解决类似的全文检索问题。或者考虑利用 InnoDB 的表都是[**聚簇**](https://bohans.gitbook.io/ji-chu/mysql/sql-you-hua/suo-yin/ju-cu-suo-yin)表的特点，采取一种轻量级别的解决方式：**一般情况下，索引都会比表小，扫描索引要比扫描表更快**，而 InnoDB 表上**二级索引** idx\_last\_name 实际上存储字段 last\_name 还有主键 actor\_id，那么**理想的访问方式应该是首先扫描二级索引 idx\_last\_name 获得满足条件 last\_name LIKE '%NI%' 的主键 actor\_id 列表，之后根据主键回表去检索记录，这样访问避开了全表扫描演员表 actor 产生的大量 IO 请求**。

  <pre class="language-sql"><code class="lang-sql">EXPLAIN
  <strong>SELECT *
  </strong>FROM (SELECT actor_id FROM actor WHERE last_name LIKE '%NI%') a,
       actor b
  WHERE a.actor_id = b.actor_id \G;
  </code></pre>

  ```
  *************************** 1. row ***************************
             id: 1
    select_type: SIMPLE
          table: actor
     partitions: NULL
           type: index
  possible_keys: PRIMARY
            key: idx_actor_last_name
        key_len: 182
            ref: NULL
           rows: 200
       filtered: 11.11
          Extra: Using where; Using index
  *************************** 2. row ***************************
             id: 1
    select_type: SIMPLE
          table: b
     partitions: NULL
           type: eq_ref
  possible_keys: PRIMARY
            key: PRIMARY
        key_len: 2
            ref: sakila.actor.actor_id
           rows: 1
       filtered: 100.00
          Extra: NULL
  ```

  从执行计划中能够看到，内层查询的 <mark style="color:blue;">**Using index**</mark> 代表<mark style="color:blue;">**索引覆盖**</mark>扫描，之后通过主键 join 操作去 actor 表中获取最终查询结果，理论上是能够比直接全表扫描更快一些。
* <mark style="color:blue;">**数据类型出现隐式转换的时候**</mark>也不会使用索引，特别是<mark style="color:orange;">**当列类型是字符串，那么一定记得在 where 条件中把字符常量值用引号引起来，否则即便这个列上有索引，MySQL 也不会用到，因为 MySQL 默认把输入的常量值进行转换以后才进行检索**</mark>。例如，演员表 actor 中的姓氏字段 last\_name 是字符型的，但是 SQL 语句中的条件值 1 是一个数值型值，因此即便存在索引 idx\_last\_name，MySQL 也不能正确地用上索引，而是继续进行全表扫描：

  ```sql
  EXPLAIN
  SELECT *
  FROM actor
  WHERE last_name = 1 \G;
  ```

  ```
  *************************** 1. row ***************************
             id: 1
    select_type: SIMPLE
          table: actor
     partitions: NULL
           type: ALL
  possible_keys: idx_actor_last_name
            key: NULL
        key_len: NULL
            ref: NULL
           rows: 200
       filtered: 10.00
          Extra: Using where
  ```

  加上引号之后，再次检查执行计划，就发现使用上索引了：

  ```sql
  EXPLAIN
  SELECT *
  FROM actor
  WHERE last_name = "1" \G;
  ```

  ```
  *************************** 1. row ***************************
             id: 1
    select_type: SIMPLE
          table: actor
     partitions: NULL
           type: ref
  possible_keys: idx_actor_last_name
            key: idx_actor_last_name
        key_len: 182
            ref: const
           rows: 1
       filtered: 100.00
          Extra: NULL
  ```
* 复合索引的情况下，假如查询条件不包含索引列最左边部分，即<mark style="color:blue;">**不满足最左前缀原则**</mark>，是不会使用复合索引的。
* 如果 <mark style="color:blue;">**MySQL 估计使用索引比全表扫描更慢**</mark>，则不使用索引。
* 用 OR 分割开的条件，**如果 OR 前的条件中的列有索引，而后面的列中没有索引**，那么涉及的索引都不会被用到。<br>

  ```sql
  EXPLAIN
  SELECT *
  FROM payment
  WHERE customer_id = 203
     OR amount = 3.96 \G;
  ```

  ```
  *************************** 1. row ***************************
             id: 1
    select_type: SIMPLE
          table: payment
     partitions: NULL
           type: ALL
  possible_keys: idx_fk_customer_id
            key: NULL
        key_len: NULL
            ref: NULL
           rows: 16086
       filtered: 10.15
          Extra: Using where
  ```

  **因为 OR 后面的条件列中没有索引，那么后面的查询肯定要走全表扫描，在存在全表扫描的情况下，就没有必要多一次索引扫描增加 I/O 访问，一次全表扫描过滤条件就足够了。**

## 查看索引使用情况

如果索引正在工作，<mark style="color:blue;">**Handler\_read\_key**</mark> 的值将很高，这个值代表了<mark style="color:orange;">**一个行被索引值读的次数，很低的值表明增加索引得到的性能改善不高，因为索引并不经常使用**</mark>。

<mark style="color:blue;">**Handler\_read\_rnd\_next**</mark> 的<mark style="color:orange;">**值高则意味着查询运行低效**</mark>，并且应该建立索引补救。这个值的含义是在数据文件中读下一行的请求数。如果正进行大量的表扫描，Handler\_read\_rnd\_next 的值较高，则通常说明表索引不正确或写入的查询没有利用索引。

<pre class="language-sql"><code class="lang-sql"><strong>mysql> SHOW STATUS WHERE variable_name LIKE "Handler_%";
</strong>+----------------------------+-------+
| Variable_name              | Value |
+----------------------------+-------+
| Handler_commit             | 7     |
| Handler_delete             | 0     |
| Handler_discover           | 0     |
| Handler_external_lock      | 16    |
| Handler_mrr_init           | 0     |
| Handler_prepare            | 0     |
| Handler_read_first         | 0     |
| Handler_read_key           | 0     |
| Handler_read_last          | 0     |
| Handler_read_next          | 0     |
| Handler_read_prev          | 0     |
| Handler_read_rnd           | 0     |
| Handler_read_rnd_next      | 0     |
| Handler_rollback           | 0     |
| Handler_savepoint          | 0     |
| Handler_savepoint_rollback | 0     |
| Handler_update             | 0     |
| Handler_write              | 0     |
+----------------------------+-------+
</code></pre>

## 自适应 HASH 索引

InnoDB 存储引擎有一个被称为自适应哈希索引的特性。<mark style="color:blue;">**当 InnoDB 发现某些索引值被非常频繁地被访问时，它会在原有的 B-tree 索引之上，在内存中再构建一个哈希索引。**</mark>这就让 B-tree 索引也具备了一些哈希索引的优势，例如，可以实现非常快速的哈希查找。<mark style="color:blue;">**这个过程是完全自动化的**</mark>，用户无法进行控制或者配置。不过，可以通过参数彻底关闭自适应哈希索引这个特性。

## 索引的优点

B-tree 索引，按照顺序存储数据，所以 MySQL 可以用来做 ORDER BY 和 GROUP BY 操作。因为数据是有序的，所以 B-tree 也就会将相关的列值都存储在一起。最后，因为索引中存储了实际的列值，所以某些查询只使用索引就能够完成全部查询。

据此特性，总结下来索引有如下三个优点：

* <mark style="color:blue;">**索引大大减少了服务器需要扫描的数据量。**</mark>
* <mark style="color:blue;">**索引可以帮助服务器避免排序和临时表。**</mark>
* <mark style="color:blue;">**索引可以将随机 I/O 变为顺序 I/O。**</mark>