本系列文章目錄 展開/收起
- Mysql索引篇（一） 索引的資料結構B+樹
- Mysql索引篇（二） Myisam和Innodb的索引
- Mysql索引篇（三） 善于explain分析sql語句
- Mysql索引篇（四） 覆寫索引(Using index)、檔案排序(Using filesort)和臨時表(Using temporary)
- Mysql索引篇（五） Sql優化建議和例子
索引是什麼，下面是mysql的官方定義：
“索引是幫助mysql高效擷取資料的排好序的資料結構”。 抓重點，索引的本質是一種資料結構,而且是排好序的。索引作用有2個，一個是排序，一個是快速查找，而快速查找的基礎就是排好了序的索引。
那麼索引可以有哪些資料結構：
二叉樹、紅黑樹、hash表和B-Tree
二叉樹索引
下面我們以二叉樹這種資料結構的索引為例，說明索引是如何工作的：
假如現在有一張表，表裡面有兩個字段 Col1 和 Col2：
現在我查詢一個sql： select * from t where col2=89;
在不使用索引情況下，mysql會從頭周遊表t，一條條的往下查詢，并比對 col2 字段是否為89。
如果使用了二叉樹索引，在對col2字段建立索引的時候，mysql會将col2字段的所有内容以二叉樹的資料結構寫入到一個索引檔案中。
我們知道二叉樹其實是由連結清單變形而來的，是由多個節點和連結指向構成的。在二叉樹索引中，每一個節點都存儲着key和value，key是從來col2的值（89），value是col2這個字段所在行的磁盤位址（0x07,0x56之類的）。
二叉樹的特點就是一個節點的右子節點的key比左子節點的key大，通過二叉樹進行查找的時間複雜度是 O(log2n)，而不用二叉樹通過周遊的方式查找的複雜度是 O(n)。是以在二叉樹中可以快速找到 key 為 89 的節點，擷取到這個節點的value（存儲col2 = 89的行所在的磁盤空間位址），然後再從這個位址中擷取col2=89這一行的所有字段的資料。
樹上的每一個索引節點都被配置設定一個磁盤空間位址，也就是說一棵樹的所有節點都是存在一塊磁盤上的不同位置。每一個父節點都有兩條單向連結指向左右子節點，單向連結存儲着子節點的磁盤位址。父節點A可以通過單向連結上記錄的磁盤位址找到子節點B的位置。
查找一個索引的時候需要将樹的節點中的資料從磁盤加載到記憶體，這就會發生一次磁盤IO操作。如果這個節點的key不是我要找的索引值，就會根據單向連結中存的磁盤位址找到子節點的磁盤空間，讀取到記憶體，這也是一次IO操作。
是以，從根節點每往下找一層子節點就是一次IO操作。
如果二叉樹這種資料結構是按字段值從小到大或者從大到小的順序來建構的話,就會完全退化為一個單向連結清單，複雜度就又變回了O(n)，和全表掃描一行行周遊沒什麼差別。
例如，對上圖中的col1這個字段建立二叉樹索引就會發生這種情況。
結論：二叉樹建構索引可能會退化為一個接近單向連結清單的結構，此時查找和排序的複雜度與全表掃描沒有什麼差別。是以二叉樹不适合作為索引的資料結構
紅黑樹索引
紅黑樹的本質是一個二叉平衡樹。紅黑樹每添加一個節點（例如是節點A）會檢查該節點A左右兩邊的子分支是否平衡，如果該節點A的右邊的層級大于該節點左邊的層級超過2層，就會做一個節點的平衡（左旋），使得該節點A節點的左右兩邊的層數相等。
而紅黑樹的自動平衡功能可以解決二叉樹退化為單向連結清單的問題
以上圖中col1字段建立紅黑樹索引為例：
紅黑樹的複雜度也是 O(log2n)，它的特點是添加或者删除節點的時候會自動平衡。
但是，用紅黑樹作為mysql資料表的索引還是存在問題的。
你想想看一個幾百萬的表用紅黑樹建構索引，這棵樹就會有很多很多層，因為紅黑樹畢竟是一個二叉樹，每個節點隻能有兩個分叉，是以資料一多，樹的層級就多。當查找一個key比較大的資料時，就要從根節點一直找到底層葉節點，效率還是不高。當資料表中的記錄數越多，紅黑樹的層級越高，查詢效率就越低。
舉個例子，用紅黑樹建構一個有100多萬資料的表的索引，那麼這個紅黑樹大概有20層。假如我查找的資料剛好在葉子節點，意味着我要在紅黑樹上查20個節點才能找到底層。
每往下層去周遊一個節點就是一次IO操作，就會發生20次磁盤io。
是以紅黑樹的瓶頸在于層數可能太多。我們希望能夠在建立幾百萬的索引的基礎上把樹的層級控制在3~4層之内。
結論：紅黑樹構 建索引的瓶頸在于存儲大表索引時，樹層級太多，導緻查找發生的io次數多。
B-Tree索引（多叉平衡樹）
B-Tree在紅黑樹的基礎上采用了 橫向擴充的優化。普通二叉樹和紅黑樹的一個節點隻能存一個索引（一個節點的磁盤空間隻存一個key-value資料），而B-Tree的每個節點可以存儲多個索引（給一個節點配置設定一個大一些的磁盤空間存多個key-value資料）。是以B-Tree的每個節點可以有多個單向連結。
接下來我們看看一個保持在3層的B-Tree的建構過程
B Tree的特點
1. 所有的葉子節點的層級都是一樣的且葉節點從左到右key是排好序的是遞增的，例如上面 所有葉子節點都是在第三層。
2. B樹的每個節點雖然有多個連結指向，但是每個索引還是隻有2個連結指向，每一個索引構成的子樹都滿足二叉樹的特性（右子節點比左子節點的key大）。
3. 單個節點内的多個索引是遞增的有排序的。當往B樹中插入一個索引的時候，索引被插入到一個節點會在這個節點中和其他索引進行排序排列。
結論：B樹的橫向擴充特性就很好的解決了紅黑樹層數過高的問題，但mysql還是沒有選擇B樹作為索引的資料結果，原因是B樹無法高效的做到範圍查找。
B+Tree索引
B+ 樹符合B Tree的所有特性。但是B+ Tree 的非葉子節點不存儲value，隻存儲key（key就是索引字段的字段值，value是該索引字段對應的行的磁盤位址或者是索引所在行的其他列的實際資料，value存什麼是因存儲引擎的類型而異的）。這使得每個非葉子節點可以存放更多的索引（因為不存value節省了空間）。
B+樹的每一個葉子節點之間維護這一個雙向連結，這個雙向連結存儲着相鄰葉節點的磁盤空間位址，使得相鄰的葉節點可以找到對方的磁盤所在位置。
葉子節點會包含所有的索引字段的key和value。部分子節點的key會備援存儲一份在父節點中。
B+樹的一個節點在磁盤中表現為一個資料頁，在添加或者删除行的時候導緻的節點平衡（頁分裂）。
一個節點中的每一個索引的兩條連結指針存儲着其子節點的磁盤位址。
B+樹的結構如下圖
B+ 樹的查找也是從根節點開始往下查。以查找上圖中的53為例：
B+ Tree 的根節點是直接存在記憶體中的，是以第一個節點無需從磁盤讀到記憶體。Mysql通過一定的算法（比如二分查找）得出53在50和66這兩個索引之間，于是擷取50和66之間的單向連結，這個連結存儲着根節點的一個子節點的磁盤空間位址。于是根據這個位址從磁盤中讀取[52 66]這個子節點的資料到記憶體。在記憶體中進行查找運算得到53在52和66之間，于是又擷取到連結找到[52 53]這個葉節點，加載到記憶體，得到53号索引對應的value值。
B樹和B+樹通過橫向擴充的方式讓樹保持一個比較層級，那麼有一個問題：既然樹的層級越低，查找索引的IO操作次數越少的話，可不可以将所有索引的key-value都放在一個節點中，這樣就隻有1層了？
首先要知道，在樹中查找一個索引的時候，需要将節點從磁盤加載到記憶體中。如果幾千萬個索引都放在一個節點（大概會有幾百兆）。一來為了找1個索引而把所有索引的資料加載到記憶體會很浪費記憶體；二來幾百兆的資料從磁盤寫到記憶體的速度也要很長時間。
是以這樣做的效率很低很笨。
對于mysql而言，樹的一個節點（無論是葉子節點還是非葉子節點）會被配置設定一個16K的大小的頁來存多個索引，一個節點就是一個資料頁。
我們可以檢視mysql一頁有多大
mysql> show global status like "Innodb_page_size";
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| Innodb_page_size | 16384 |
+------------------+-------+
我們從磁盤取行資料加載到記憶體的時候，不可能是從磁盤讀一行資料到記憶體又再回到磁盤再讀一行資料到記憶體，這樣頻繁的發生io效率會很低。是以實際情況是，每次從磁盤讀取資料到記憶體的最小機關是一個頁（B+樹中一個節點），是以有時候雖然你隻想查一行，但是還是會把一個頁給讀取到記憶體。
那麼一棵B+樹能存多少個索引（多少條行）呢？
以innodb表的主鍵索引為例，一個整型id大概占8B，每個索引的連結指針占6B，16K/14B = 1170; 是以一個非葉子節點大概能放1170個索引。而葉子節點儲存着value和雙向指針，假設value是索引字段所在行的其他字段的實際資料（假設平均是1K，指針大概占12B，可以忽略不計），那麼一個葉子節點最多隻有16個索引。
那麼一棵3層的B+ Tree，大概能存儲 1170117016 = 兩千多萬 條資料。
是以兩千多萬條資料如果通過B+ Tree建立索引，要查找一行資料也就進行2次磁盤IO即可（因為B+樹的根節點一般是直接加載在記憶體中的），花的時間也就兩次IO的時間。
如果資料超過2千多萬，那就增加 B+ 樹的層數為4層即可。
Hash表索引
如果以Hash結構作為索引，mysql會建立一個hash表，這個hash表是這樣的：先對索引列的值進行一個hash散列函數的計算得到一個散列值，以這個散列值作為key，以索引所在的行資料的磁盤位址作為value。将key和value存在一個高速的映射表中。這樣下次根據索引查找行的時候就可以快速找到行所在的位址。
對于where條件為精确查找（where in/=）來說，hash表的結構比B+樹的性能高。但是對于範圍查找（>/</between）來說，還是要對mysql表進行逐行周遊，一個個的通過hash函數計算得到散列值， 再通過散列值查hash表的value。
B+樹是怎麼進行範圍查找的呢？這全靠B+樹葉子節點之間的雙向指針和葉子節點是有序的這兩個特性。例如做出where id > 30 這樣的範圍查詢，mysql會先通過B+樹的查找算法找到30所在的葉子節點A，然後通過葉子節點A的雙向連結找到了它右邊相鄰節點B的位址，然後通過B的連結找到了B的右邊相鄰節點C的位址，一直這樣找下去，就擷取到了 id > 30的資料。
考慮到同是兼顧精确查找和範圍查找mysql還是使用了B+樹而不用hash表。
B+ 樹和B樹的差別在于兩點：
1. B樹的葉子節點之間沒有雙向指針，不支援範圍查找，如果B樹要進行範圍查找的話必須多次從根節點往下找;
2. B樹的非葉子節點包含了value，但是B+樹的非葉子節點隻有key沒有value，由于B樹的非葉子節點包含value就意味着相同層數的B樹和B+樹，B樹能存儲的索引個數遠小于B+樹。同樣是3層數，B+數可以存 1170 * 1170 * 16 = 兩千多萬個索引，而B樹隻能存 161616 = 4096個索引。如果用B樹結構存一張兩千多萬的大表的索引，就需要大概7層。
不論是二叉樹，紅黑樹，B樹還是B+樹，他們都是對資料排好序的結構，排好序的索引是高效查找的前提。“排好序”展現在一個節點的key比左節點的key大，比右節點的key小（葉子節點從左到右的key是從小到大的）。這也應了本文的第一句話：“索引是幫助mysql高效擷取資料的排好序的資料結構”
本文轉載自：
張柏沛IT技術部落格 > Mysql索引篇（一） 索引的資料結構B+樹