了解下B-tree索引

了解下B-tree索引

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

我們使用術(shù)語“B-Tree”，是因?yàn)镸ySQL在CREATE TABLE和其他語句中也使用該關(guān)鍵字。不過，底層的存儲引擎也可能使用不同的存儲結(jié)構(gòu)，例如，NDB集群存儲引擎內(nèi)部實(shí)際上使用了T-tree結(jié)構(gòu)存儲這種索引，即使期名字是BTREE;InnoDB則使用的是B+Tree，各種數(shù)據(jù)結(jié)構(gòu)和算法的變種在這里不討論。

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

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

B-Tree索引能夠加快訪問數(shù)據(jù)的速度，因?yàn)榇鎯σ娌辉傩枰M(jìn)行全表掃描來獲取需要的數(shù)據(jù)，取而代之的是從索引的根節(jié)點(diǎn)開始進(jìn)行搜索。根節(jié)點(diǎn)的槽中存放了指向子節(jié)點(diǎn)的指針，存儲引擎根據(jù)這些指針向下層查找。通過比較節(jié)點(diǎn)頁的值和要查找的值找到合適的指針進(jìn)行下層子節(jié)點(diǎn)，這些指針實(shí)際上定義了子節(jié)點(diǎn)中值的上限和下限。最終存儲引擎要么是找到對應(yīng)的值，要么該記錄不存在。葉子節(jié)點(diǎn)比較特別，他們的指針指向的是被索引的數(shù)據(jù)，而不是其他的節(jié)點(diǎn)頁（不同引擎的“指針”類型不同）。上圖僅繪制了一個節(jié)點(diǎn)和其對應(yīng)的葉子節(jié)點(diǎn)，其實(shí)在根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之間可能有很多層節(jié)點(diǎn)頁。樹的深度和表的大小直接相關(guān)。

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

假如有如下數(shù)據(jù)表：

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)

);

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

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

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

*全值匹配

*匹配最左前綴

*匹配列前綴

*匹配范圍值

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

因?yàn)樗饕龢渲械墓?jié)點(diǎn)是有序的，所以除了按值查找之外，索引還可以用于查詢中的ORDER BY操作（按順序查找）。一般來說，如果B_TREE可以按照某種方式查找到值，那么也可以按照這種方式用于排序。所以，如果order by子句滿足前面列出的幾種查詢類型，則這個索引也可以滿足對應(yīng)的排序需求。

下面是一些關(guān)于B_TREE索引的限制

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

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

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

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

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

作者：黑馬程序員JavaEE培訓(xùn)學(xué)院
首發(fā)：http://java.itheima.com/