前言

本節(jié)課程思維導圖：

作為一個軟件開發(fā)工程師，你對數(shù)據(jù)庫肯定再熟悉不過了。作為主流的數(shù)據(jù)存儲系統(tǒng)，它在我們的業(yè)務開發(fā)中，有著舉足輕重的地位。在工作中，為了加速數(shù)據(jù)庫中數(shù)據(jù)的查找速度，我們常用的處理思路是，對表中數(shù)據(jù)創(chuàng)建索引。那你是否思考過，數(shù)據(jù)庫索引是如何實現(xiàn)的呢？底層使用的是什么數(shù)據(jù)結(jié)構(gòu)和算法呢？

算法解析

思考的過程比結(jié)論更重要。今天的講解，我會盡量還原這個解決方案的思考過程，讓你知其然，并且知其所以然。

1. 解決問題的前提是定義清楚問題

如何定義清楚問題呢？除了對問題進行詳細的調(diào)研，還有一個辦法，那就是，通過對一些模糊的需求進行假設，來限定要解決的問題的范圍。

如果你對數(shù)據(jù)庫的操作非常了解，針對我們現(xiàn)在這個問題，你就能把索引的需求定義得非常清楚。但是，對于大部分軟件工程師來說，我們可能只了解一小部分常用的 SQL 語句，所以，這里我們假設要解決的問題，只包含這樣兩個常用的需求：
根據(jù)某個值查找數(shù)據(jù)，比如 select * from user where id=1234；
根據(jù)區(qū)間值來查找某些數(shù)據(jù)，比如 select * from user where id > 1234 and id < 2345。

除了這些功能性需求之外，這種問題往往還會涉及一些非功能性需求，比如安全、性能、用戶體驗等等。限于專欄要討論的主要是數(shù)據(jù)結(jié)構(gòu)和算法，對于非功能性需求，我們著重考慮性能方面的需求。性能方面的需求，我們主要考察時間和空間兩方面，也就是執(zhí)行效率和存儲空間。在執(zhí)行效率方面，我們希望通過索引，查詢數(shù)據(jù)的效率盡可能地高；在存儲空間方面，我們希望索引不要消耗太多的內(nèi)存空間。

2. 嘗試用學過的數(shù)據(jù)結(jié)構(gòu)解決這個問題
   問題的需求大致定義清楚了，我們現(xiàn)在回想一下，能否利用已經(jīng)學習過的數(shù)據(jù)結(jié)構(gòu)解決這個問題呢？支持快速查詢、插入等操作的動態(tài)數(shù)據(jù)結(jié)構(gòu)，我們已經(jīng)學習過散列表、平衡二叉查找樹、跳表。

我們先來看散列表。散列表的查詢性能很好，時間復雜度是 O(1)。但是，散列表不能支持按照區(qū)間快速查找數(shù)據(jù)。所以，散列表不能滿足我們的需求。

我們再來看平衡二叉查找樹。盡管平衡二叉查找樹查詢的性能也很高，時間復雜度是 O(logn)。而且，對樹進行中序遍歷，我們還可以得到一個從小到大有序的數(shù)據(jù)序列，但這仍然不足以支持按照區(qū)間快速查找數(shù)據(jù)。

我們再來看跳表。跳表是在鏈表之上加上多層索引構(gòu)成的。它支持快速地插入、查找、刪除數(shù)據(jù)，對應的時間復雜度是 O(logn)。并且，跳表也支持按照區(qū)間快速地查找數(shù)據(jù)。我們只需要定位到區(qū)間起點值對應在鏈表中的結(jié)點，然后從這個結(jié)點開始，順序遍歷鏈表，直到區(qū)間終點對應的結(jié)點為止，這期間遍歷得到的數(shù)據(jù)就是滿足區(qū)間值的數(shù)據(jù)。

這樣看來，跳表是可以解決這個問題。實際上，數(shù)據(jù)庫索引所用到的數(shù)據(jù)結(jié)構(gòu)跟跳表非常相似，叫作 B+ 樹。不過，它是通過二叉查找樹演化過來的，而非跳表。為了給你還原發(fā)明 B+ 樹的整個思考過程，所以，接下來，我還要從二叉查找樹講起，看它是如何一步一步被改造成 B+ 樹的。

3. 改造二叉查找樹來解決這個問題。
   為了讓二叉查找樹支持按照區(qū)間來查找數(shù)據(jù)，我們可以對它進行這樣的改造：樹中的節(jié)點并不存儲數(shù)據(jù)本身，而是只是作為索引。除此之外，我們把每個葉子節(jié)點串在一條鏈表上，鏈表中的數(shù)據(jù)是從小到大有序的。經(jīng)過改造之后的二叉樹，就像圖中這樣，看起來是不是很像跳表呢？

改造之后，如果我們要求某個區(qū)間的數(shù)據(jù)。我們只需要拿區(qū)間的起始值，在樹中進行查找，當查找到某個葉子節(jié)點之后，我們再順著鏈表往后遍歷，直到鏈表中的結(jié)點數(shù)據(jù)值大于區(qū)間的終止值為止。所有遍歷到的數(shù)據(jù)，就是符合區(qū)間值的所有數(shù)據(jù)。

但是，我們要為幾千萬、上億的數(shù)據(jù)構(gòu)建索引，如果將索引存儲在內(nèi)存中，盡管內(nèi)存訪問的速度非?？?，查詢的效率非常高，但是，占用的內(nèi)存會非常多。比如，我們給一億個數(shù)據(jù)構(gòu)建二叉查找樹索引，那索引中會包含大約 1 億個節(jié)點，每個節(jié)點假設占用 16 個字節(jié)，那就需要大約 1GB 的內(nèi)存空間。給一張表建立索引，我們需要 1GB 的內(nèi)存空間。如果我們要給 10 張表建立索引，那對內(nèi)存的需求是無法滿足的。如何解決這個索引占用太多內(nèi)存的問題呢？

我們可以借助時間換空間的思路，把索引存儲在硬盤中，而非內(nèi)存中。我們都知道，硬盤是一個非常慢速的存儲設備。通常內(nèi)存的訪問速度是納秒級別的，而磁盤訪問的速度是毫秒級別的。讀取同樣大小的數(shù)據(jù)，從磁盤中讀取花費的時間，是從內(nèi)存中讀取所花費時間的上萬倍，甚至幾十萬倍。這種將索引存儲在硬盤中的方案，盡管減少了內(nèi)存消耗，但是在數(shù)據(jù)查找的過程中，需要讀取磁盤中的索引，因此數(shù)據(jù)查詢效率就相應降低很多。

二叉查找樹，經(jīng)過改造之后，支持區(qū)間查找的功能就實現(xiàn)了。不過，為了節(jié)省內(nèi)存，如果把樹存儲在硬盤中，那么每個節(jié)點的讀?。ɑ蛘咴L問），都對應一次磁盤 IO 操作。樹的高度就等于每次查詢數(shù)據(jù)時磁盤 IO 操作的次數(shù)。

我們前面講到，比起內(nèi)存讀寫操作，磁盤 IO 操作非常耗時，所以我們優(yōu)化的重點就是盡量減少磁盤 IO 操作，也就是，盡量降低樹的高度。那如何降低樹的高度呢？

我們來看下，如果我們把索引構(gòu)建成 m 叉樹，高度是不是比二叉樹要小呢？如圖所示，給 16 個數(shù)據(jù)構(gòu)建二叉樹索引，樹的高度是 4，查找一個數(shù)據(jù)，就需要 4 個磁盤 IO 操作（如果根節(jié)點存儲在內(nèi)存中，其他節(jié)點存儲在磁盤中），如果對 16 個數(shù)據(jù)構(gòu)建五叉樹索引，那高度只有 2，查找一個數(shù)據(jù)，對應只需要 2 次磁盤操作。如果 m 叉樹中的 m 是 100，那對一億個數(shù)據(jù)構(gòu)建索引，樹的高度也只是 3，最多只要 3 次磁盤 IO 就能獲取到數(shù)據(jù)。磁盤 IO 變少了，查找數(shù)據(jù)的效率也就提高了。

如果我們將 m 叉樹實現(xiàn) B+ 樹索引，用代碼實現(xiàn)出來，就是下面這個樣子（假設我們給 int 類型的數(shù)據(jù)庫字段添加索引，所以代碼中的 keywords 是 int 類型的）：

/**
 * 這是B+樹非葉子節(jié)點的定義。
 *
 * 假設keywords=[3, 5, 8, 10]
 * 4個鍵值將數(shù)據(jù)分為5個區(qū)間：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
 * 5個區(qū)間分別對應：children[0]...children[4]
 *
 * m值是事先計算得到的，計算的依據(jù)是讓所有信息的大小正好等于頁的大?。? * PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
 */
public class BPlusTreeNode {
  public static int m = 5; // 5叉樹
  public int[] keywords = new int[m-1]; // 鍵值，用來劃分數(shù)據(jù)區(qū)間
  public BPlusTreeNode[] children = new BPlusTreeNode[m];//保存子節(jié)點指針
}

/**
 * 這是B+樹中葉子節(jié)點的定義。
 *
 * B+樹中的葉子節(jié)點跟內(nèi)部節(jié)點是不一樣的,
 * 葉子節(jié)點存儲的是值，而非區(qū)間。
 * 這個定義里，每個葉子節(jié)點存儲3個數(shù)據(jù)行的鍵值及地址信息。
 *
 * k值是事先計算得到的，計算的依據(jù)是讓所有信息的大小正好等于頁的大?。? * PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
 */
public class BPlusTreeLeafNode {
  public static int k = 3;
  public int[] keywords = new int[k]; // 數(shù)據(jù)的鍵值
  public long[] dataAddress = new long[k]; // 數(shù)據(jù)地址

  public BPlusTreeLeafNode prev; // 這個結(jié)點在鏈表中的前驅(qū)結(jié)點
  public BPlusTreeLeafNode next; // 這個結(jié)點在鏈表中的后繼結(jié)點
}

對于相同個數(shù)的數(shù)據(jù)構(gòu)建 m 叉樹索引，m 叉樹中的 m 越大，那樹的高度就越小，那 m 叉樹中的 m 是不是越大越好呢？到底多大才最合適呢？

不管是內(nèi)存中的數(shù)據(jù)，還是磁盤中的數(shù)據(jù)，操作系統(tǒng)都是按頁（一頁大小通常是 4KB，這個值可以通過 getconfig PAGE_SIZE 命令查看）來讀取的，一次會讀一頁的數(shù)據(jù)。如果要讀取的數(shù)據(jù)量超過一頁的大小，就會觸發(fā)多次 IO 操作。所以，我們在選擇 m 大小的時候，要盡量讓每個節(jié)點的大小等于一個頁的大小。讀取一個節(jié)點，只需要一次磁盤 IO 操作。

盡管索引可以提高數(shù)據(jù)庫的查詢效率，但是，作為一名開發(fā)工程師，你應該也知道，索引有利也有弊，它也會讓寫入數(shù)據(jù)的效率下降。這是為什么呢？數(shù)據(jù)的寫入過程，會涉及索引的更新，這是索引導致寫入變慢的主要原因。

對于一個 B+ 樹來說，m 值是根據(jù)頁的大小事先計算好的，也就是說，每個節(jié)點最多只能有 m 個子節(jié)點。在往數(shù)據(jù)庫中寫入數(shù)據(jù)的過程中，這樣就有可能使索引中某些節(jié)點的子節(jié)點個數(shù)超過 m，這個節(jié)點的大小超過了一個頁的大小，讀取這樣一個節(jié)點，就會導致多次磁盤 IO 操作。我們該如何解決這個問題呢？

實際上，處理思路并不復雜。我們只需要將這個節(jié)點分裂成兩個節(jié)點。但是，節(jié)點分裂之后，其上層父節(jié)點的子節(jié)點個數(shù)就有可能超過 m 個。不過這也沒關系，我們可以用同樣的方法，將父節(jié)點也分裂成兩個節(jié)點。這種級聯(lián)反應會從下往上，一直影響到根節(jié)點。這個分裂過程，你可以結(jié)合著下面這個圖一塊看，會更容易理解（圖中的 B+ 樹是一個三叉樹。我們限定葉子節(jié)點中，數(shù)據(jù)的個數(shù)超過 2 個就分裂節(jié)點；非葉子節(jié)點中，子節(jié)點的個數(shù)超過 3 個就分裂節(jié)點）。

正是因為要時刻保證 B+ 樹索引是一個 m 叉樹，所以，索引的存在會導致數(shù)據(jù)庫寫入的速度降低。實際上，不光寫入數(shù)據(jù)會變慢，刪除數(shù)據(jù)也會變慢。這是為什么呢？

我們在刪除某個數(shù)據(jù)的時候，也要對應地更新索引節(jié)點。這個處理思路有點類似跳表中刪除數(shù)據(jù)的處理思路。頻繁的數(shù)據(jù)刪除，就會導致某些節(jié)點中，子節(jié)點的個數(shù)變得非常少，長此以往，如果每個節(jié)點的子節(jié)點都比較少，勢必會影響索引的效率。

我們可以設置一個閾值。在 B+ 樹中，這個閾值等于 m/2。如果某個節(jié)點的子節(jié)點個數(shù)小于 m/2，我們就將它跟相鄰的兄弟節(jié)點合并。不過，合并之后節(jié)點的子節(jié)點個數(shù)有可能會超過 m。針對這種情況，我們可以借助插入數(shù)據(jù)時候的處理方法，再分裂節(jié)點。

文字描述不是很直觀，我舉了一個刪除操作的例子，你可以對比著看下（圖中的 B+ 樹是一個五叉樹。我們限定葉子節(jié)點中，數(shù)據(jù)的個數(shù)少于 2 個就合并節(jié)點；非葉子節(jié)點中，子節(jié)點的個數(shù)少于 3 個就合并節(jié)點。）。

數(shù)據(jù)庫索引以及 B+ 樹的由來，到此就講完了。你有沒有發(fā)現(xiàn)，B+ 樹的結(jié)構(gòu)和操作，跟跳表非常類似。理論上講，對跳表稍加改造，也可以替代 B+ 樹，作為數(shù)據(jù)庫的索引實現(xiàn)的。

總結(jié)引申

今天，我們講解了數(shù)據(jù)庫索引實現(xiàn)，依賴的底層數(shù)據(jù)結(jié)構(gòu)，B+ 樹。它通過存儲在磁盤的多叉樹結(jié)構(gòu)，做到了時間、空間的平衡，既保證了執(zhí)行效率，又節(jié)省了內(nèi)存。

前面的講解中，為了一步一步詳細地給你介紹 B+ 樹的由來，內(nèi)容看起來比較零散。為了方便你掌握和記憶，我這里再總結(jié)一下 B+ 樹的特點：

• 每個節(jié)點中子節(jié)點的個數(shù)不能超過 m，也不能小于 m/2；
• 根節(jié)點的子節(jié)點個數(shù)可以不超過 m/2，這是一個例外；
• m 叉樹只存儲索引，并不真正存儲數(shù)據(jù)，這個有點兒類似跳表；
• 通過鏈表將葉子節(jié)點串聯(lián)在一起，這樣可以方便按區(qū)間查找；
• 一般情況，根節(jié)點會被存儲在內(nèi)存中，其他節(jié)點存儲在磁盤中。

除了 B+ 樹，你可能還聽說過 B 樹、B- 樹，我這里簡單提一下。實際上，B- 樹就是 B 樹，英文翻譯都是 B-Tree，這里的“-”并不是相對 B+ 樹中的“+”，而只是一個連接符。這個很容易誤解，所以我強調(diào)下。

而 B 樹實際上是低級版的 B+ 樹，或者說 B+ 樹是 B 樹的改進版。B 樹跟 B+ 樹的不同點主要集中在這幾個地方：

• B+ 樹中的節(jié)點不存儲數(shù)據(jù)，只是索引，而 B 樹中的節(jié)點存儲數(shù)據(jù)；
• B 樹中的葉子節(jié)點并不需要鏈表來串聯(lián)。

也就是說，B 樹只是一個每個節(jié)點的子節(jié)點個數(shù)不能小于 m/2 的 m 叉樹。文章來源地址http://www.zghlxwxcb.cn/news/detail-793474.html

到了這里，關于數(shù)據(jù)結(jié)構(gòu)與算法之美學習筆記：48 | B+樹：MySQL數(shù)據(jù)庫索引是如何實現(xiàn)的？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！