淺談MySQL的B樹索引與索引優(yōu)化小結(jié)

MySQL的MyISAM、InnoDB引擎默認均使用B+樹索引（查詢時都顯示為“BTREE”），本文討論兩個問題：

1. 為什么MySQL等主流數(shù)據(jù)庫選擇B+樹的索引結(jié)構(gòu)？
2. 如何基于索引結(jié)構(gòu)，理解常見的MySQL索引優(yōu)化思路？

為什么索引無法全部裝入內(nèi)存

索引結(jié)構(gòu)的選擇基于這樣一個性質(zhì)：大數(shù)據(jù)量時，索引無法全部裝入內(nèi)存。

為什么索引無法全部裝入內(nèi)存？假設(shè)使用樹結(jié)構(gòu)組織索引，簡單估算一下：

1. 假設(shè)單個索引節(jié)點12B，1000w個數(shù)據(jù)行，unique索引，則葉子節(jié)點共占約100MB，整棵樹最多200MB。
2. 假設(shè)一行數(shù)據(jù)占用200B，則數(shù)據(jù)共占約2G。

假設(shè)索引存儲在內(nèi)存中。也就是說，每在物理盤上保存2G的數(shù)據(jù)，就要占用200MB的內(nèi)存，索引:數(shù)據(jù)的占用比約為1/10。1/10的占用比算不算大呢？物理盤比內(nèi)存廉價的多，以一臺內(nèi)存16G硬盤1T的服務(wù)器為例，如果要存滿1T的硬盤，至少需要100G的內(nèi)存，遠大于16G。

考慮到一個表上可能有多個索引、聯(lián)合索引、數(shù)據(jù)行占用更小等情況，實際的占用比通常大于1/10，某些時候能達到1/3。在基于索引的存儲架構(gòu)中，索引:數(shù)據(jù)的占用比過高，因此，索引無法全部裝入內(nèi)存。

其他結(jié)構(gòu)的問題

由于無法裝入內(nèi)存，則必然依賴磁盤（或SSD）存儲。而內(nèi)存的讀寫速度是磁盤的成千上萬倍（與具體實現(xiàn)有關(guān)），因此，核心問題是“如何減少磁盤讀寫次數(shù)”。

首先不考慮頁表機制，假設(shè)每次讀、寫都直接穿透到磁盤，那么：

1. 線性結(jié)構(gòu)：讀/寫平均O(n)次
2. 二叉搜索樹（BST）：讀/寫平均O(log2(n))次；如果樹不平衡，則最差讀/寫O(n)次
3. 自平衡二叉搜索樹（AVL）：在BST的基礎(chǔ)上加入了自平衡算法，讀/寫最大O(log2(n))次
4. 紅黑樹（RBT）：另一種自平衡的查找樹，讀/寫最大O(log2(n))次

BST、AVL、RBT很好的將讀寫次數(shù)從O(n)優(yōu)化到O(log2(n))；其中，AVL和RBT都比BST多了自平衡的功能，將讀寫次數(shù)降到最大O(log2(n))。

假設(shè)使用自增主鍵，則主鍵本身是有序的，樹結(jié)構(gòu)的讀寫次數(shù)能夠優(yōu)化到樹高，樹高越低讀寫次數(shù)越少；自平衡保證了樹結(jié)構(gòu)的穩(wěn)定。如果想進一步優(yōu)化，可以引入B樹和B+樹。

B樹解決了什么問題

很多文章將B樹誤稱為B-（減）樹，這可能是對其英文名“B-Tree”的誤解（更有甚者，將B樹稱為二叉樹或二叉搜索樹）。特別是與B+樹一起講的時候。想當然的認為有B+（加）樹就有B-（減）樹，實際上B+樹的英文名是“B+-Tree”。

如果拋開維護操作，那么B樹就像一棵“m叉搜索樹”（m是子樹的最大個數(shù)），時間復雜度為O(logm(n))。然而，B樹設(shè)計了一種高效簡單的維護操作，使B樹的深度維持在約log(ceil(m/2))(n)~logm(n)之間，大大降低樹高。

再次強調(diào)：

不要糾結(jié)于時間復雜度，與單純的算法不同，磁盤IO次數(shù)才是更大的影響因素。讀者可以推導看看，B樹與AVL的時間復雜度是相同的，但由于B樹的層數(shù)少，磁盤IO次數(shù)少，實踐中B樹的性能要優(yōu)于AVL等二叉樹。

同二叉搜索樹類似，每個節(jié)點存儲了多個key和子樹，子樹與key按順序排列。

頁表的目錄是擴展外存+加速磁盤讀寫，一個頁（Page）通常4K（等于磁盤數(shù)據(jù)塊block的大小，見inode與block的分析），操作系統(tǒng)每次以頁為單位將內(nèi)容從磁盤加載到內(nèi)存（以攤分尋道成本），修改頁后，再擇期將該頁寫回磁盤?？紤]到頁表的良好性質(zhì)，可以使每個節(jié)點的大小約等于一個頁（使m非常大），這每次加載的一個頁就能完整覆蓋一個節(jié)點，以便選擇下一層子樹；對子樹同理。對于頁表來說，AVL（或RBT）相當于1個key+2個子樹的B樹，由于邏輯上相鄰的節(jié)點，物理上通常不相鄰，因此，讀入一個4k頁，頁面內(nèi)絕大部分空間都將是無效數(shù)據(jù)。

假設(shè)key、子樹節(jié)點指針均占用4B，則B樹節(jié)點最大m * (4 + 4) = 8m B；頁面大小4KB。則m = 4 * 1024 / 8m = 512，一個512叉的B樹，1000w的數(shù)據(jù)，深度最大 log(512/2)(10^7) = 3.02 ~= 4。對比二叉樹如AVL的深度為log(2)(10^7) = 23.25 ~= 24，相差了5倍以上。震驚！B樹索引深度竟然如此！

另外，B樹對局部性原理非常友好。如果key比較?。ū热缟厦?B的自增key），則除了頁表的加成，緩存還能進一步預(yù)讀加速。美滋滋~

B+樹解決了什么問題

B樹的剩余問題

然而，如果要實際應(yīng)用到數(shù)據(jù)庫的索引中，B樹還有一些問題：

1. 未定位數(shù)據(jù)行
2. 無法處理范圍查詢

問題1

數(shù)據(jù)表的記錄有多個字段，僅僅定位到主鍵是不夠的，還需要定位到數(shù)據(jù)行。有3個方案解決：

1. 直接將key對應(yīng)的數(shù)據(jù)行（可能對應(yīng)多行）存儲子節(jié)點中。
2. 數(shù)據(jù)行單獨存儲；節(jié)點中增加一個字段，定位key對應(yīng)數(shù)據(jù)行的位置。
3. 修改key與子樹的判斷邏輯，使子樹大于等于上一key小于下一key，最終所有訪問都將落于葉子節(jié)點；葉子節(jié)點中直接存儲數(shù)據(jù)行或數(shù)據(jù)行的位置。

方案1直接pass，存儲數(shù)據(jù)行將減少頁面中的子樹個數(shù)，m減小樹高增大。

方案2的節(jié)點中增加了一個字段，假設(shè)是4B的指針，則新的m = 4 * 1024 / 12m = 341.33 ~= 341，深度最大 log(341/2)(10^7) = 3.14 ~= 4。

方案3的節(jié)點m與深度不變，但時間復雜度變?yōu)榉€(wěn)定的O(logm(n))。

方案3可以考慮。

問題2

實際業(yè)務(wù)中，范圍查詢的頻率非常高，B樹只能定位到一個索引位置（可能對應(yīng)多行），很難處理范圍查詢。改動較小的是2個

方案：

1. 不改動；查詢的時候先查到左界，再查到右界，然后DFS（或BFS）遍歷左界、右界之間的節(jié)點。
2. 在“問題1-方案3”的基礎(chǔ)上，由于所有數(shù)據(jù)行都存儲在葉子節(jié)點，B樹的葉子節(jié)點本身也是有序的，可以增加一個指針，指向當前葉子節(jié)點按主鍵順序的下一葉子節(jié)點；查詢時先查到左界，再查到右界，然后從左界到有界線性遍歷。

乍一看感覺方案1比方案2好——時間復雜度和常數(shù)項都一樣，方案1還不需要改動。但是別忘了局部性原理，不管節(jié)點中存儲的是數(shù)據(jù)行還是數(shù)據(jù)行位置，方案2的好處在于，依然可以利用頁表和緩存預(yù)讀下一節(jié)點的信息。而方案1則面臨節(jié)點邏輯相鄰、物理分離的缺點。

引出B+樹

綜上，問題1的方案2與問題2的方案1可整合為一種方案（基于B樹的索引），問題1的方案3與問題2的方案2可整合為一種（基于B+樹的索引）。實際上，數(shù)據(jù)庫、文件系統(tǒng)有些采用了B樹，有些采用B+樹。

由于某些猴子暫未明白的原因，包括MySQL在內(nèi)的主流數(shù)據(jù)庫多選擇了B+樹。即：

主要變動如上所述：

1. 修改key與子樹的組織邏輯，將索引訪問都落到葉子節(jié)點
2. 按順序?qū)⑷~子節(jié)點串起來（方便范圍查詢）

B樹和B+樹的增、刪、查過程

B樹的增刪過程暫時可參考從B樹、B+樹、B*樹談到R 樹的“6、B樹的插入、刪除操作”小節(jié)，B+樹的增刪同理。此處暫不贅述。

Mysql索引優(yōu)化

根據(jù)B+樹的性質(zhì)，很容易理解各種常見的MySQL索引優(yōu)化思路。

暫不考慮不同引擎之間的區(qū)別。

優(yōu)先使用自增key作為主鍵

前面的分析中，假設(shè)用4B的自增key作為索引，則m可達到512，層高僅有3。使用自增的key有兩個好處：

自增key一般為int等整數(shù)型，key比較緊湊，這樣m可以非常大，而且索引占用空間小。最極端的例子，如果使用50B的varchar（包括長度），那么m = 4 * 1024 / 54m = 75.85 ~= 76，深度最大 log(76/2)(10^7) = 4.43 ~= 5，再加上cache缺失、字符串比較的成本，時間成本增加較大。同時，key由4B增長到50B，整棵索引樹的空間占用增長也是極為恐怖的（如果二級索引使用主鍵定位數(shù)據(jù)行，則空間增長更加嚴重）。

自增的性質(zhì)使得新數(shù)據(jù)行的插入請求必然落到索引樹的最右側(cè)，發(fā)生節(jié)點分裂的頻率較低，理想情況下，索引樹可以達到“滿”的狀態(tài)。索引樹滿，一方面層高更低，一方面刪除節(jié)點時發(fā)生節(jié)點合并的頻率也較低。

優(yōu)化經(jīng)歷：

猴子曾使用varchar(100)的列做過主鍵，存儲containerId，過了3、4天100G的數(shù)據(jù)庫就滿了，DBA小姐姐郵件里委婉表示了對我的鄙視。。。之后增加了自增列作為主鍵，containerId作為unique的二級索引，時間、空間優(yōu)化效果相當顯著。

最左前綴匹配

索引可以簡單如一個列(a)，也可以復雜如多個列(a, b, c, d)，即聯(lián)合索引。如果是聯(lián)合索引，那么key也由多個列組成，同時，索引只能用于查找key是否存在（相等），遇到范圍查詢(>、<、between、like左匹配)等就不能進一步匹配了，后續(xù)退化為線性查找。因此，列的排列順序決定了可命中索引的列數(shù)。

如有索引(a, b, c, d)，查詢條件a = 1 and b = 2 and c > 3 and d = 4，則會在每個節(jié)點依次命中a、b、c，無法命中d。也就是最左前綴匹配原則。

=、in自動優(yōu)化順序

不需要考慮=、in等的順序，mysql會自動優(yōu)化這些條件的順序，以匹配盡可能多的索引列。

如有索引(a, b, c, d)，查詢條件c > 3 and b = 2 and a = 1 and d < 4與a = 1 and c > 3 and b = 2 and d < 4等順序都是可以的，MySQL會自動優(yōu)化為a = 1 and b = 2 and c > 3 and d < 4，依次命中a、b、c。

索引列不能參與計算

有索引列參與計算的查詢條件對索引不友好（甚至無法使用索引），如from_unixtime(create_time) = '2014-05-29'。

原因很簡單，如何在節(jié)點中查找到對應(yīng)key？如果線性掃描，則每次都需要重新計算，成本太高；如果二分查找，則需要針對from_unixtime方法確定大小關(guān)系。

因此，索引列不能參與計算。上述from_unixtime(create_time) = '2014-05-29'語句應(yīng)該寫成create_time = unix_timestamp('2014-05-29')。

能擴展就不要新建索引

如果已有索引(a)，想建立索引(a, b)，盡量選擇修改索引(a)為索引(a, b)。

新建索引的成本很容易理解。而基于索引(a)修改為索引(a, b)的話，MySQL可以直接在索引a的B+樹上，經(jīng)過分裂、合并等修改為索引(a, b)。

不需要建立前綴有包含關(guān)系的索引

如果已有索引(a, b)，則不需要再建立索引(a)，但是如果有必要，則仍然需考慮建立索引(b)。

選擇區(qū)分度高的列作索引

很容易理解。如，用性別作索引，那么索引僅能將1000w行數(shù)據(jù)劃分為兩部分（如500w男，500w女），索引幾乎無效。

區(qū)分度的公式是count(distinct <col>) / count(*)，表示字段不重復的比例，比例越大區(qū)分度越好。唯一鍵的區(qū)分度是1，而一些狀態(tài)、性別字段可能在大數(shù)據(jù)面前的區(qū)分度趨近于0。

這個值很難確定，一般需要join的字段要求是0.1以上，即平均1條掃描10條記錄。

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持億速云。