了解下B-tree索引

當人們討論索引的時候，如果沒有特別指明類型，那多半說的是B-tree索引，他使用B-tree數據結構來存儲數據，大多數MYSQL引擎都支持這種索引，Archive引擎是一個例外：5.1之前Archive不支持任何索引，直到5.1才開始支持單個自增列（AUTO_INCREMENT）的索引。

我們使用術語“B-Tree”，是因為MySQL在CREATE TABLE和其他語句中也使用該關鍵字。不過，底層的存儲引擎也可能使用不同的存儲結構，例如，NDB集群存儲引擎內部實際上使用了T-tree結構存儲這種索引，即使期名字是BTREE;InnoDB則使用的是B+Tree，各種數據結構和算法的變種在這里不討論。

存儲引擎以不同的方式使用B-Tree索引，性能也各有不同，各有優劣。例如，MyISAM使用前綴壓縮技術使得索引更小，但InnoDB則按照原數據格式進行存儲，再如MyISAM索引通過數據的物理位置引用被索引的行，而InnoDB則根據主鍵引用被索引的行。

B-Tree通常意味著所有的值都是按順序存儲的，并且每一個葉子頁到根的距離相同。下圖展示了B-Tree索引的抽象表示，大致反映了InnoDB索引是如何工作的。MyISAM使用的結構有所不同，但基本思想是類似的。

B-Tree索引能夠加快訪問數據的速度，因為存儲引擎不再需要進行全表掃描來獲取需要的數據，取而代之的是從索引的根節點開始進行搜索。根節點的槽中存放了指向子節點的指針，存儲引擎根據這些指針向下層查找。通過比較節點頁的值和要查找的值找到合適的指針進行下層子節點，這些指針實際上定義了子節點中值的上限和下限。最終存儲引擎要么是找到對應的值，要么該記錄不存在。葉子節點比較特別，他們的指針指向的是被索引的數據，而不是其他的節點頁（不同引擎的“指針”類型不同）。上圖僅繪制了一個節點和其對應的葉子節點，其實在根節點和葉子節點之間可能有很多層節點頁。樹的深度和表的大小直接相關。

  BTree對索引列是順序組織存儲的，所以很適合查找范圍數據。例如，在一個基于文本域的索引樹上，按字母順序傳遞連續的值進行查找是非常合適的，所以像“找出所有以I到K開頭的名字”這樣的查找效率會非常高。

假如有如下數據表：

CREATE TABLE People(

Last_name varchar(50)  not null,

first_name varchar(50)  not null,

Dob      date       not null,

Gender   enum(‘m’,’f’) not null,

Key(last_name,first_name,dob)

);

對于表中的每一行數據，索引中包含了last_name,first_name和dob列的值，下圖顯示了該索引是如何組織數據的存儲的。

請注意，索引對多個值進行排序的依據是CREATE TABLE語句中的定義索引時列的順序，看下面最后兩條目，兩個人的姓和名都一樣，則根據他們的出生日期來排序順序。

可以使用B-Tree索引的查詢類型，B-Tree索引適用于全鍵值，鍵值范圍或鍵前綴查找。其中鍵前綴查找只適用于根據最左前綴的查找。前面所述的索引對如下類型的查詢有效。

*全值匹配

*匹配最左前綴

*匹配列前綴

*匹配范圍值

*精確匹配某一列并范圍匹配另外一列

因為索引樹中的節點是有序的，所以除了按值查找之外，索引還可以用于查詢中的ORDER BY操作（按順序查找）。一般來說，如果B_TREE可以按照某種方式查找到值，那么也可以按照這種方式用于排序。所以，如果order by子句滿足前面列出的幾種查詢類型，則這個索引也可以滿足對應的排序需求。

下面是一些關于B_TREE索引的限制

1:如果不是按照索引的最左列開始查找，則無法使用索引。例如上面例子中的索引無法用于查找名字為BILL的人，也無法查找某個特定生日的人，因為這兩列都不是最左數據列。類似地，也無法查找姓氏以某個字母結尾的人。

2：不能跳過索引中的列，也就是說，前面所述的索引無法用于查找姓為Smith并且在某個特定日期出生的人。如果不指定名（first_name）,則MYSQL只能使用索引的第一列。

3：如果查詢中有某個列的范圍查詢，則其右邊所有列都無法使用索引優化查找。例如喲查詢where last_name=’Smith’ AND first_name Like ‘J%’ AND dob =’1976-12-23’，這個查詢只能使用索引的前兩列，因為這里LIKE是一個范圍條件（但是服務器可以把其余列用于其他目的）。如果范圍查詢列值的數量有限，那么可以通過使用多個等于條件來代替范圍條件。

到這里，前面提到的索引列的順序是多么的重要：這些限制都和索引列的順序有關。在優化性能的時候，可能需要使用相同的列但順序不同的索引來滿足不同類型的查詢需求。

也有些限制并不是B-Tree本身導致的，而是Mysql優化器和存儲引擎使用索引的方式導致的，這部分限制在未來的版本中可能就不再是限制了。

作者：黑馬程序員JavaEE培訓學院
首發：http://java.itheima.com/