不少朋友留言問MySQL索引底層的實現(xiàn)，讓我講講B+樹。知其然，知其所以然，講懂B+樹其實不難，今天更多聊聊“數(shù)據(jù)庫索引，為什么設(shè)計成這樣”。

問題1. 數(shù)據(jù)庫為什么要設(shè)計索引?

圖書館存了1000W本圖書，要從中找到《架構(gòu)師之路》，一本本查，要查到什么時候去?于是，圖書管理員設(shè)計了一套規(guī)則：

• 一樓放歷史類，二樓放文學(xué)類，三樓放IT類…
• IT類，又分軟件類，硬件類…
• 軟件類，又按照書名排序…

以便快速找到一本書。 與之類比，數(shù)據(jù)庫存儲了1000W條數(shù)據(jù)，要從中找到name=”shenjian”的記錄，一條條查，要查到什么時候去?

于是，要有索引，用于提升數(shù)據(jù)庫的查找速度。

問題2. 哈希(hash)比樹(tree)更快，索引結(jié)構(gòu)為什么要設(shè)計成樹型?

加速查找速度的數(shù)據(jù)結(jié)構(gòu)，常見的有兩類：

• 哈希，例如HashMap，查詢/插入/修改/刪除的平均時間復(fù)雜度都是O(1);
• 樹，例如平衡二叉搜索樹，查詢/插入/修改/刪除的平均時間復(fù)雜度都是O(lg(n));

可以看到，不管是讀請求，還是寫請求，哈希類型的索引，都要比樹型的索引更快一些，那為什么，索引結(jié)構(gòu)要設(shè)計成樹型呢?

畫外音：80%的同學(xué)，面試都答不出來。

索引設(shè)計成樹形，和SQL的需求相關(guān)。

對于這樣一個單行查詢的SQL需求：

select * from t where name=”shenjian”; 

確實是哈希索引更快，因為每次都只查詢一條記錄。

畫外音：所以，如果業(yè)務(wù)需求都是單行訪問，例如passport，確實可以使用哈希索引。

但是對于排序查詢的SQL需求：

• 分組：group by
• 排序：order by
• 比較：<、>
• …

哈希型的索引，時間復(fù)雜度會退化為O(n)，而樹型的“有序”特性，依然能夠保持O(log(n)) 的高效率。

任何脫離需求的設(shè)計都是耍流氓。

多說一句，InnoDB并不支持手動建立哈希索引。

畫外音：自適應(yīng)hash索引，是InnoDB內(nèi)核機制。

問題3. 數(shù)據(jù)庫索引為什么使用B+樹?

為了保持知識體系的完整性，簡單介紹下幾種樹。

第一種：二叉搜索樹

二叉搜索樹，如上圖，是最為大家所熟知的一種數(shù)據(jù)結(jié)構(gòu)，就不展開介紹了，它為什么不適合用作數(shù)據(jù)庫索引?

• 當數(shù)據(jù)量大的時候，樹的高度會比較高，數(shù)據(jù)量大的時候，查詢會比較慢;
• 每個節(jié)點只存儲一個記錄，可能導(dǎo)致一次查詢有很多次磁盤IO;

畫外音：這個樹經(jīng)常出現(xiàn)在大學(xué)課本里，所以最為大家所熟知。

第二種：B樹

B樹，如上圖，它的特點是：

• 不再是二叉搜索，而是m叉搜索;
• 葉子節(jié)點，非葉子節(jié)點，都存儲數(shù)據(jù);
• 中序遍歷，可以獲得所有節(jié)點;

畫外音，實在不想介紹這個特性：非根節(jié)點包含的關(guān)鍵字個數(shù)j滿足，(┌m/2┐)-1 <= j <= m-1，節(jié)點分裂時要滿足這個條件。

B樹被作為實現(xiàn)索引的數(shù)據(jù)結(jié)構(gòu)被創(chuàng)造出來，是因為它能夠完美的利用“局部性原理”。

(1) 什么是局部性原理?

局部性原理的邏輯是這樣的：

• 內(nèi)存讀寫塊，磁盤讀寫慢，而且慢很多;
• 磁盤預(yù)讀：磁盤讀寫并不是按需讀取，而是按頁預(yù)讀，一次會讀一頁的數(shù)據(jù)，每次加載更多的數(shù)據(jù)，如果未來要讀取的數(shù)據(jù)就在這一頁中，可以避免未來的磁盤IO，提高效率;

畫外音：通常，操作系統(tǒng)一頁數(shù)據(jù)是4K，MySQL的一頁是16K。

• 局部性原理：軟件設(shè)計要盡量遵循“數(shù)據(jù)讀取集中”與“使用到一個數(shù)據(jù)，大概率會使用其附近的數(shù)據(jù)”，這樣磁盤預(yù)讀能充分提高磁盤IO;

(2) B樹為何適合做索引?

• 由于是m分叉的，高度能夠大大降低;
• 每個節(jié)點可以存儲j個記錄，如果將節(jié)點大小設(shè)置為頁大小，例如4K，能夠充分的利用預(yù)讀的特性，極大減少磁盤IO;

第三種：B+樹

B+樹，如上圖，仍是m叉搜索樹，在B樹的基礎(chǔ)上，做了一些改進：

(1)非葉子節(jié)點不再存儲數(shù)據(jù)，數(shù)據(jù)只存儲在同一層的葉子節(jié)點上;

畫外音：B+樹中根到每一個節(jié)點的路徑長度一樣，而B樹不是這樣。

(2)葉子之間，增加了鏈表，獲取所有節(jié)點，不再需要中序遍歷;

這些改進讓B+樹比B樹有更優(yōu)的特性：

• 范圍查找，定位min與max之后，中間葉子節(jié)點，就是結(jié)果集，不用中序回溯;畫外音：范圍查詢在SQL中用得很多，這是B+樹比B樹最大的優(yōu)勢。
• 葉子節(jié)點存儲實際記錄行，記錄行相對比較緊密的存儲，適合大數(shù)據(jù)量磁盤存儲;非葉子節(jié)點存儲記錄的PK，用于查詢加速，適合內(nèi)存存儲;
• 非葉子節(jié)點，不存儲實際記錄，而只存儲記錄的KEY的話，那么在相同內(nèi)存的情況下，B+樹能夠存儲更多索引;

最后，量化說下，為什么m叉的B+樹比二叉搜索樹的高度大大大大降低?

大概計算一下：

(1)局部性原理，將一個節(jié)點的大小設(shè)為一頁，一頁4K，假設(shè)一個KEY有8字節(jié)，一個節(jié)點可以存儲500個KEY，即j=500;

(2)m叉樹，大概m/2<= j <=m，即可以差不多是1000叉樹;

(3)那么：

一層樹：1個節(jié)點，1*500個KEY，大小4K

二層樹：1000個節(jié)點，1000*500=50W個KEY，大小1000*4K=4M

三層樹：1000*1000個節(jié)點，1000*1000*500=5億個KEY，大小1000*1000*4K=4G

畫外音：額，幫忙看下有沒有算錯。

可以看到，存儲大量的數(shù)據(jù)(5億)，并不需要太高樹的深度(高度3)，索引也不是太占內(nèi)存(4G)。

總結(jié)

(1)數(shù)據(jù)庫索引用于加速查詢;

(2)雖然哈希索引是O(1)，樹索引是O(log(n))，但SQL有很多“有序”需求，故數(shù)據(jù)庫使用樹型索引;

(3)InnoDB不支持手動創(chuàng)建哈希索引;

(4)數(shù)據(jù)預(yù)讀的思路是：磁盤讀寫并不是按需讀取，而是按頁預(yù)讀，一次會讀一頁的數(shù)據(jù)，每次加載更多的數(shù)據(jù)，以便未來減少磁盤IO

(5)局部性原理：軟件設(shè)計要盡量遵循“數(shù)據(jù)讀取集中”與“使用到一個數(shù)據(jù)，大概率會使用其附近的數(shù)據(jù)”，這樣磁盤預(yù)讀能充分提高磁盤IO

(6)數(shù)據(jù)庫的索引最常用B+樹：

• 很適合磁盤存儲，能夠充分利用局部性原理，磁盤預(yù)讀;
• 很低的樹高度，能夠存儲大量數(shù)據(jù);
• 索引本身占用的內(nèi)存很小;
• 能夠很好的支持單點查詢，范圍查詢，有序性查詢;

【本文為51CTO專欄作者“58沈劍”原創(chuàng)稿件，轉(zhuǎn)載請聯(lián)系原作者】

戳這里，看該作者更多好文