B-Tree 索引類型詳解

索引有很多種類型，可以為不同的應(yīng)用場(chǎng)景提供更好的性能。在 MySQL 中，索引是在存儲(chǔ)引擎層實(shí)現(xiàn)的。接下來(lái)重點(diǎn)介紹四種常見的索引類型：B-Tree 索引、哈希索引、空間數(shù)據(jù)索引（R-Tree）、全文索引。這部分內(nèi)容分為上下兩個(gè)小節(jié)，本小節(jié)重點(diǎn)介紹 B-Tree 索引。

1. B-Tree 索引

B-Tree 索引是最常見的索引之一，當(dāng)大家在談?wù)撍饕臅r(shí)候，如果沒(méi)有特別說(shuō)明，那多半說(shuō)的就是 B-Tree 索引。在 MySQL 中，大多數(shù)的存儲(chǔ)引擎都支持 B-Tree 索引。

1.1 存儲(chǔ)結(jié)構(gòu)

B-Tree 對(duì)索引列的值是按順序存儲(chǔ)的，并且每一個(gè)葉子頁(yè)到根的距離相同。B-Tree 索引可以加快數(shù)據(jù)查找的速度，因?yàn)榇鎯?chǔ)引擎不需要全表掃描來(lái)獲取數(shù)據(jù)，只要從索引的根節(jié)點(diǎn)開始搜索即可。

以表 customer 為例，我們來(lái)看看索引是如何組織數(shù)據(jù)的存儲(chǔ)的。

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)
     );

如圖，對(duì)于表中的每行數(shù)據(jù)，索引包含了 last_name、first_name 和 birth_date 的值。

1.2 適合 B-Tree 索引的查詢類型

全值匹配

和索引中的所有列進(jìn)行匹配，如查找姓名為 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: ref
possible_keys: idx1_customer
          key: idx1_customer
      key_len: 190
          ref: const,const,const
         rows: 1
     filtered: 100.00
        Extra: NULL
1 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: ref
possible_keys: idx1_customer
          key: idx1_customer
      key_len: 93
          ref: const
         rows: 1
     filtered: 100.00
        Extra: NULL
1 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: range
possible_keys: idx1_customer
          key: idx1_customer
      key_len: 93
          ref: NULL
         rows: 1
     filtered: 100.00
        Extra: Using index condition
1 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: range
possible_keys: idx1_customer
          key: idx1_customer
      key_len: 93
          ref: NULL
         rows: 1
     filtered: 100.00
        Extra: Using index condition
1 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: range
possible_keys: idx1_customer
          key: idx1_customer
      key_len: 186
          ref: NULL
         rows: 1
     filtered: 100.00
        Extra: Using index condition
1 row in set, 1 warning (0.00 sec)

只訪問(wèn)索引的查詢

只需要訪問(wèn)索引即可獲取數(shù)據(jù)，不需要回表訪問(wèn)數(shù)據(jù)行，這種查詢也叫覆蓋索引：

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

除了上述這些查詢類型外，索引還可以用于 order by 排序操作，因?yàn)樗饕械墓?jié)點(diǎn)是有序的。如果 B-Tree 可以按照某種方式查找到數(shù)據(jù)，那么也可以按照這種方式進(jìn)行排序。

1.3 B-Tree 索引的限制

如果不是按照索引的最左列開始查找數(shù)據(jù)，則無(wú)法使用索引。如查找名字為 George 的客戶：

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

不能跳過(guò)索引的列。如查找姓氏為 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: ref
possible_keys: idx1_customer
          key: idx1_customer
      key_len: 93
          ref: const
         rows: 1
     filtered: 100.00
        Extra: Using index condition
1 row in set, 1 warning (0.00 sec)

如果查詢中有某個(gè)列的范圍查詢，在其右邊的列都無(wú)法使用索引進(jìn)行查找數(shù)據(jù)。如查找姓氏為以 B 開頭，名字為 George 的客戶。這個(gè)查詢只能使用第一列，因?yàn)?like 是一個(gè)范圍查詢：

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: range
possible_keys: idx1_customer
          key: idx1_customer
      key_len: 186
          ref: NULL
         rows: 1
     filtered: 100.00
        Extra: Using index condition
1 row in set, 1 warning (0.00 sec)

2. 小結(jié)

本小節(jié)介紹了 B-Tree 索引的存儲(chǔ)結(jié)構(gòu)、適合 B-Tree 索引的查詢類型和相關(guān)限制，從中我們可以看出，索引列的順序非常重要。在某些應(yīng)用場(chǎng)景，可能需要?jiǎng)?chuàng)建相同列，但順序不同的索引，來(lái)滿足性能的優(yōu)化。