B-Tree 索引类型详解

素颜马尾好姑娘i 2024-03-16 12:20 42阅读 0赞

### 1. B-Tree 索引 ###

B-Tree 索引是最常见的索引之一，当大家在谈论索引的时候，如果没有特别说明，那多半说的就是 B-Tree 索引。在 MySQL 中，大多数的存储引擎都支持 B-Tree 索引。

#### 1.1 存储结构 ####

B-Tree 对索引列的值是按顺序存储的，并且每一个叶子页到根的距离相同。B-Tree 索引可以加快数据查找的速度，因为存储引擎不需要全表扫描来获取数据，只要从索引的根节点开始搜索即可。

以表 customer 为例，我们来看看索引是如何组织数据的存储的。

mysql> create table customer(
    		 id int,
             last_name varchar(30),
    		 first_name varchar(30),
    		 birth_date date,
    		 gender char(1),
    		 key idx1_customer(last_name,first_name,birth_date)
         );

复制

如图，对于表中的每行数据，索引包含了 last\_name、first\_name 和 birth\_date 的值。

#### 1.2 适合 B-Tree 索引的查询类型 ####

**全值匹配**

和索引中的所有列进行匹配，如查找姓名为 George Bush、1960-08-08 出生的客户。

mysql> explain select * from customer where first_name='George' and last_name='Bush' and birth_date='1960-08-08'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: refpossible_keys: idx1_customer
              key: idx1_customer
          key_len: 190
              ref: const,const,const
             rows: 1
         filtered: 100.00
            Extra: NULL1 row in set, 1 warning (0.00 sec)

复制

**匹配最左前缀**

只使用索引的第一列，如查找所有姓氏为 Bush 的客户：

mysql> explain select * from customer where last_name='Bush'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: refpossible_keys: idx1_customer
              key: idx1_customer
          key_len: 93
              ref: const
             rows: 1
         filtered: 100.00
            Extra: NULL1 row in set, 1 warning (0.00 sec)

复制

**匹配列前缀**

只匹配某一列的值的开头部分，如查找所有以 B 开头的姓氏的客户，这里使用了索引的第一列：

mysql> explain select * from customer where last_name like 'B%'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: rangepossible_keys: idx1_customer
              key: idx1_customer
          key_len: 93
              ref: NULL
             rows: 1
         filtered: 100.00
            Extra: Using index condition1 row in set, 1 warning (0.00 sec)

复制

**匹配范围值**

查找所有姓氏在 Allen 和 Bush 之间的客户，这里使用了索引的第一列：

mysql> explain select * from customer where last_name between 'Allen' and 'Bush'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: rangepossible_keys: idx1_customer
              key: idx1_customer
          key_len: 93
              ref: NULL
             rows: 1
         filtered: 100.00
            Extra: Using index condition1 row in set, 1 warning (0.00 sec)

复制

**精确匹配某一列，并范围匹配另一列**

第一列全匹配，第二列范围匹配，如查找姓氏为 Bush，名字以 G 开头的客户：

mysql> explain select * from customer where last_name='Bush' and first_name like 'G'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: rangepossible_keys: idx1_customer
              key: idx1_customer
          key_len: 186
              ref: NULL
             rows: 1
         filtered: 100.00
            Extra: Using index condition1 row in set, 1 warning (0.00 sec)

复制

**只访问索引的查询**

只需要访问索引即可获取数据，不需要回表访问数据行，这种查询也叫覆盖索引：

mysql> explain select last_name from customer where last_name='Bush'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: refpossible_keys: idx1_customer
              key: idx1_customer
          key_len: 93
              ref: const
             rows: 1
         filtered: 100.00
            Extra: Using index1 row in set, 1 warning (0.00 sec)

复制

除了上述这些查询类型外，索引还可以用于 order by 排序操作，因为索引中的节点是有序的。如果 B-Tree 可以按照某种方式查找到数据，那么也可以按照这种方式进行排序。

#### 1.3 B-Tree 索引的限制 ####

如果不是按照索引的最左列开始查找数据，则无法使用索引。如查找名字为 George 的客户：

mysql> explain select * from customer where first_name='George'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: ALLpossible_keys: NULL
              key: NULL
          key_len: NULL
              ref: NULL
             rows: 1
         filtered: 100.00
            Extra: Using where1 row in set, 1 warning (0.00 sec)

复制

不能跳过索引的列。如查找姓氏为 Bush，生日为 1960-08-08 的客户，这种查询只能使用索引的第一列：

mysql> explain select * from customer where last_name='Bush' and birth_date='1960-08-08'\G*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: refpossible_keys: idx1_customer
              key: idx1_customer
          key_len: 93
              ref: const
             rows: 1
         filtered: 100.00
            Extra: Using index condition1 row in set, 1 warning (0.00 sec)

复制

如果查询中有某个列的范围查询，在其右边的列都无法使用索引进行查找数据。如查找姓氏为以 B 开头，名字为 George 的客户。这个查询只能使用第一列，因为 like 是一个范围查询：

mysql> explain select * from customer where last_name like 'B%' and first_name='George'\G;*************************** 1. row ***************************
               id: 1
      select_type: SIMPLE
            table: customer
       partitions: NULL
             type: rangepossible_keys: idx1_customer
              key: idx1_customer
          key_len: 186
              ref: NULL
             rows: 1
         filtered: 100.00
            Extra: Using index condition1 row in set, 1 warning (0.00 sec)