為什麼MySQL用B+樹做索引

碼農老K

工具主管,科技領域創作者

索引這個詞，相信大多數人已經相當熟悉了，很多人都知道MySQL的索引主要以B+樹為主，但是要問到為什麼用B+樹，恐怕很少有人能把前因後果講述的很完整。本文就來從頭到尾介紹下數據庫的索引。

索引是一種數據結構，用於幫助我們在大量數據中快速定位到我們想要查找的數據。 索引最形象的比喻就是圖書的目錄了。注意這裏的大量，數據量大了索引才顯得有意義，如果我想要在<1,2,3,4>中找到4這個數據，直接對全數據檢索也很快，沒有必要費力氣建索引再去查找。索引在mysql數據庫中分三類：

B+樹索引、Hash索引、全文索引

我們今天要介紹的是工作開發中最常接觸到innodb存儲引擎中的的B+樹索引。

要介紹B+樹索引，就不得不提二叉查找樹，平衡二叉樹和B樹這三種數據結構。B+樹就是從他們仨演化來的。

二叉查找樹

首先，讓我們先看一張圖

從圖中可以看到，我們為user表（用戶信息表）建立了一個二叉查找樹的索引。圖中的圓為二叉查找樹的節點，節點中存儲了鍵(key)和數據(data)。

鍵對應user表中的id，數據對應user表中的行數據。二叉查找樹的特點就是任何節點的左子節點的鍵值都小於當前節點的鍵值，右子節點的鍵值都大於當前節點的鍵值。 頂端的節點我們稱為根節點，沒有子節點的節點我們稱之為葉節點。

如果我們需要查找id=12的用戶信息，利用我們創建的二叉查找樹索引，查找流程如下：

1. 將根節點作為當前節點，把12與當前節點的鍵值10比較，12大於10，接下來我們把當前節點>的右子節點作為當前節點。2. 繼續把12和當前節點的鍵值13比較，發現12小於13，把當前節點的左子節點作為當前節點。3. 把12和當前節點的鍵值12對比，12等於12，滿足條件，我們從當前節點中取出data，即id=12,name=xm。

利用二叉查找樹我們只需要3次即可找到匹配的數據。如果在表中一條條的查找的話，我們需要6次才能找到。

平衡二叉樹

上面我們講解了利用二叉查找樹可以快速的找到數據。但是，如果上面的二叉查找樹是這樣的構造：

這個時候可以看到我們的二叉查找樹變成了一個鏈表。

如果我們需要查找id=17的用戶信息，我們需要查找7次，也就相當於全表掃描了。

導致這個現象的原因其實是二叉查找樹變得不平衡了，也就是高度太高了，從而導致查找效率的不穩定。

為了解決這個問題，我們需要保證二叉查找樹一直保持平衡，就需要用到平衡二叉樹了。

平衡二叉樹又稱AVL樹，在滿足二叉查找樹特性的基礎上，要求每個節點的左右子樹的高度差不能超過1。

下面是平衡二叉樹和非平衡二叉樹的對比：

由平衡二叉樹的構造我們可以發現第一張圖中的二叉樹其實就是一棵平衡二叉樹。

平衡二叉樹保證了樹的構造是平衡的，當我們插入或刪除數據導致不滿足平衡二叉樹不平衡時，平衡二叉樹會進行調整樹上的節點來保持平衡。具體的調整方式這裏就不介紹了。

平衡二叉樹相比於二叉查找樹來說，查找效率更穩定，總體的查找速度也更快。

B樹

因為內存的易失性。一般情況下，我們都會選擇將user表中的數據和索引存儲在磁盤這種外圍設備中。

但是和內存相比，從磁盤中讀取數據的速度會慢上百倍千倍甚至萬倍，所以，我們應當盡量減少從磁盤中讀取數據的次數。 另外，從磁盤中讀取數據時，都是按照磁盤塊來讀取的，並不是一條一條的讀。

如果我們能把盡量多的數據放進磁盤塊中，那一次磁盤讀取操作就會讀取更多數據，那我們查找數據的時間也會大幅度降低。

如果我們用樹這種數據結構作為索引的數據結構，那我們每查找一次數據就需要從磁盤中讀取一個節點，也就是我們說的一個磁盤塊，我們都知道平衡二叉樹可是每個節點只存儲一個鍵值和數據的。

那說明什麼？

說明每個磁盤塊僅僅存儲一個鍵值和數據！

那如果我們要存儲海量的數據呢？

可以想象到二叉樹的節點將會非常多，高度也會及其高，我們查找數據時也會進行很多次磁盤IO，我們查找數據的效率將會極低！

為了解決平衡二叉樹的這個弊端，我們應該尋找一種單個節點可以存儲多個鍵值和數據的平衡樹。也就是我們接下來要說的B樹。

B樹（Balance Tree）即為平衡樹的意思，下圖即是一顆B樹。

圖中的p節點為指向子節點的指針，二叉查找樹和平衡二叉樹其實也有，因為圖的美觀性，被省略了。- 圖中的每個節點稱為頁，頁就是我們上面說的磁盤塊，在mysql中數據讀取的基本單位都是頁，所以我們這裏叫做頁更符合mysql中索引的底層數據結構。

從上圖可以看出，B樹相對於平衡二叉樹，每個節點存儲了更多的鍵值(key)和數據(data)，並且每個節點擁有更多的子節點，子節點的個數一般稱為階，上述圖中的B樹為3階B樹，高度也會很低。

基於這個特性，B樹查找數據讀取磁盤的次數將會很少，數據的查找效率也會比平衡二叉樹高很多。

假如我們要查找id=28的用戶信息，那麼我們在上圖B樹中查找的流程如下：

1. 先找到根節點也就是頁1，判斷28在鍵值17和35之間，我們那麼我們根據頁1中的指針p2找到頁3。2. 將28和頁3中的鍵值相比較，28在26和30之間，我們根據頁3中的指針p2找到頁8。3. 將28和頁8中的鍵值相比較，發現有匹配的鍵值28，鍵值28對應的用戶信息為(28,bv)。

B+樹

B+樹是對B樹的進一步優化。讓我們先來看下B+樹的結構圖：

根據上圖我們來看下B+樹和B樹有什麼不同。

1. B+樹非葉子節點上是不存儲數據的，僅存儲鍵值，而B樹節點中不僅存儲鍵值，也會存儲數據。之所以這麼做是因為在數據庫中頁的大小是固定的，innodb中頁的默認大小是16KB。如果不存儲數據，那麼就會存儲更多的鍵值，相應的樹的階數（節點的子節點樹）就會更大，樹就會更矮更胖，如此一來我們查找數據進行磁盤的IO次數有會再次減少，數據查詢的效率也會更快。另外，B+樹的階數是等於鍵值的數量的，如果我們的B+樹一個節點可以存儲1000個鍵值，那麼3層B+樹可以存儲1000×1000×1000=10億個數據。一般根節點是常駐內存的，所以一般我們查找10億數據，只需要2次磁盤IO。

2. 因為B+樹索引的所有數據均存儲在葉子節點，而且數據是按照順序排列的。那麼B+樹使得範圍查找，排序查找，分組查找以及去重查找變得異常簡單。而B樹因為數據分散在各個節點，要實現這一點是很不容易的。

有心的讀者可能還發現上圖B+樹中各個頁之間是通過雙向鏈表連接的，葉子節點中的數據是通過單向鏈表連接的。

其實上面的B樹我們也可以對各個節點加上鏈表。其實這些不是它們之前的區別，是因為在mysql的innodb存儲引擎中，索引就是這樣存儲的。也就是說上圖中的B+樹索引就是innodb中B+樹索引真正的實現方式，准確的說應該是聚集索引（聚集索引和非聚集索引下面會講到）。

通過上圖可以看到，在innodb中，我們通過數據頁之間通過雙向鏈表連接以及葉子節點中數據之間通過單向鏈表連接的方式可以找到表中所有的數據。

MyISAM中的B+樹索引實現與innodb中的略有不同。在MyISAM中，B+樹索引的葉子節點並不存儲數據，而是存儲數據的文件地址。

聚集索引 VS 非聚集索引

在上節介紹B+樹索引的時候，我們提到了圖中的索引其實是聚集索引的實現方式。那什麼是聚集索引呢？

在MySQL中，B+樹索引按照存儲方式的不同分為聚集索引和非聚集索引。

這裏我們著重介紹innodb中的聚集索引和非聚集索引。

1. 聚集索引（聚簇索引）：以innodb作為存儲引擎的表，表中的數據都會有一個主鍵，即使你不創建主鍵，系統也會幫你創建一個隱式的主鍵。這是因為innodb是把數據存放在B+樹中的，而B+樹的鍵值就是主鍵，在B+樹的葉子節點中，存儲了表中所有的數據。這種以主鍵作為B+樹索引的鍵值而構建的B+樹索引，我們稱之為聚集索引。

2. 非聚集索引（非聚簇索引）：以主鍵以外的列值作為鍵值構建的B+樹索引，我們稱之為非聚集索引。非聚集索引與聚集索引的區別在於非聚集索引的葉子節點不存儲表中的數據，而是存儲該列對應的主鍵，想要查找數據我們還需要根據主鍵再去聚集索引中進行查找，這個再根據聚集索引查找數據的過程，我們稱為回表。

明白了聚集索引和非聚集索引的定義，我們應該明白這樣一句話：數據即索引，索引即數據。

利用聚集索引和非聚集索引查找數據

前面我們講解B+樹索引的時候並沒有去說怎麼在B+樹中進行數據的查找，主要就是因為還沒有引出聚集索引和非聚集索引的概念。下面我們通過講解如何通過聚集索引以及非聚集索引查找數據表中數據的方式介紹一下B+樹索引查找數據方法。

利用聚集索引查找數據

還是這張B+樹索引圖，現在我們應該知道這就是聚集索引，表中的數據存儲在其中。現在假設我們要查找id>=18並且id<40的用戶數據。對應的sql語句為select * from user where id>=18 and id <40，其中id為主鍵。具體的查找過程如下：

1. 一般根節點都是常駐內存的，也就是說頁1已經在內存中了，此時不需要到磁盤中讀取數據，直接從內存中讀取即可。從內存中讀取到頁1，要查找這個id>=18 and id <40或者範圍值，我們首先需要找到id=18的鍵值。從頁1中我們可以找到鍵值18，此時我們需要根據指針p2，定位到頁3。2. 要從頁3中查找數據，我們就需要拿著p2指針去磁盤中進行讀取頁3。從磁盤中讀取頁3後將頁3放入內存中，然後進行查找，我們可以找到鍵值18，然後再拿到頁3中的指針p1，定位到頁8。3. 同樣的頁8頁不在內存中，我們需要再去磁盤中將頁8讀取到內存中。將頁8讀取到內存中後。因為頁中的數據是鏈表進行連接的，而且鍵值是按照順序存放的，此時可以根據二分查找法定位到鍵值18。此時因為已經到數據頁了，此時我們已經找到一條滿足條件的數據了，就是鍵值18對應的數據。因為是範圍查找，而且此時所有的數據又都存在葉子節點，並且是有序排列的，那麼我們就可以對頁8中的鍵值依次進行遍歷查找並匹配滿足條件的數據。我們可以一直找到鍵值為22的數據，然後頁8中就沒有數據了，此時我們需要拿著頁8中的p指針去讀取頁9中的數據。4. 因為頁9不在內存中，就又會加載頁9到內存中，並通過和頁8中一樣的方式進行數據的查找，直到將頁12加載到內存中，發現41大於40，此時不滿足條件。那麼查找到此終止。最終我們找到滿足條件的所有數據為：(18,kl),(19,kl),(22,hj),(24,io),(25,vg),(29,jk),(31,jk),(33,rt),(34,ty),(35,yu),(37,rt),(39,rt)。總共12條記錄。

下面看下具體的查找流程圖：

利用非聚集索引查找數據

讀者看到這張圖的時候可能會蒙，這是啥東西啊？怎麼都是數字。

如果有這種感覺，請仔細看下圖中紅字的解釋。什麼？還看不懂？那我再來解釋下吧。首先，這個非聚集索引表示的是用戶幸運數字的索引（為什麼是幸運數字？一時興起想起來的:-)），此時表結構是這樣的。

在葉子節點中，不在存儲所有的數據了，存儲的是鍵值和主鍵。

對於葉子節點中的x-y，比如1-1。左邊的1表示的是索引的鍵值，右邊的1表示的是主鍵值。如果我們要找到幸運數字為33的用戶信息，對應的sql語句為select * from user where luckNum=33。

查找的流程跟聚集索引一樣，這裏就不詳細介紹了。我們最終會找到主鍵值47，找到主鍵後我們需要再到聚集索引中查找具體對應的數據信息，此時又回到了聚集索引的查找流程。

在MyISAM中，聚集索引和非聚集索引的葉子節點都會存儲數據的文件地址。

總結

本篇文從二叉查找樹，詳細說明了為什麼mysql用B+樹作為數據的索引，以及在innodb中數據庫如何通過B+樹索引來存儲數據以及查找數據。我們一定要記住這句話：。