[[409098]]

本文轉(zhuǎn)載自微信公眾號(hào)「碼上Java」，作者碼上Java。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼上Java公眾號(hào)。  

前言

面試中經(jīng)常被問(wèn)到索引相關(guān)的問(wèn)題，其實(shí)索引這個(gè)概念非常好理解，我們?cè)谏蠈W(xué)的時(shí)候都肯定用過(guò)字典吧。索引就像字典的那個(gè)目錄，我們可以借助目錄快速檢索到我們所需要的字的解釋。同樣的道理，在數(shù)據(jù)庫(kù)中，索引也可以幫助我們快速檢索到我們所需要的數(shù)據(jù)，而且查詢的效率非常高。

總的來(lái)說(shuō)，索引就是一種數(shù)據(jù)結(jié)構(gòu)，我們今天一起來(lái)探究一下索引到底什么什么樣的?為什么我們常用B+樹(shù)最為索引的數(shù)據(jù)結(jié)構(gòu)呢?

為什么有了索引查詢就會(huì)變快?

我們都知道數(shù)據(jù)庫(kù)存儲(chǔ)有兩種存儲(chǔ)介質(zhì)，一個(gè)是內(nèi)存，另一個(gè)是硬盤(pán)。內(nèi)存是一種臨時(shí)性存儲(chǔ)介質(zhì)，而且容量也非常有限，如果服務(wù)器斷電的話，會(huì)導(dǎo)致數(shù)據(jù)丟失。硬盤(pán)是一種永久性存儲(chǔ)介質(zhì)(如果不損壞的話)，所以說(shuō)我們需要把數(shù)據(jù)存放在硬盤(pán)里面才安全。

但是有個(gè)問(wèn)題?如果我們把數(shù)據(jù)放在硬盤(pán)里面的話，我們對(duì)其中數(shù)據(jù)進(jìn)行查詢的時(shí)候，就會(huì)產(chǎn)生硬盤(pán)的I/O操作。相比于內(nèi)存存取來(lái)說(shuō)的話，硬盤(pán)在存取時(shí)I/O消耗的時(shí)間要高很多。而索引的作用就是盡量減少硬盤(pán)的I/O操作，從而降低花費(fèi)的時(shí)間。你可以對(duì)比查字典的操作，目錄(索引)可以幫你減少翻頁(yè)的動(dòng)作，一個(gè)道理。

先聊聊二叉樹(shù)

二叉樹(shù)，顧名思義，每個(gè)節(jié)點(diǎn)最多有兩個(gè)“叉”，也就是兩個(gè)子節(jié)點(diǎn)，分別是左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。不過(guò)，二叉樹(shù)并不要求每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，有的節(jié)點(diǎn)只有左子節(jié)點(diǎn)，有的節(jié)點(diǎn)只有右子節(jié)點(diǎn)。

我們先來(lái)看下一個(gè)最基礎(chǔ)的二叉搜索樹(shù)(Binary Search Tree)，搜索某個(gè)節(jié)點(diǎn)和插入節(jié)點(diǎn)的規(guī)則一樣，我們假設(shè)搜索插入的數(shù)值為 key：

• 如果 key 大于根節(jié)點(diǎn)，則在右子樹(shù)中進(jìn)行查找;
• 如果 key 小于根節(jié)點(diǎn)，則在左子樹(shù)中進(jìn)行查找;
• 如果 key 等于根節(jié)點(diǎn)，也就是找到了這個(gè)節(jié)點(diǎn)，返回根節(jié)點(diǎn)即可。

我們舉個(gè)例子，創(chuàng)建數(shù)列{30，25，36，32，40，20，28}，同樣的數(shù)據(jù)，不同的插入順序，樹(shù)的結(jié)果是不一樣的，如下圖所示：

但是存在極端的情況，當(dāng)二叉樹(shù)的深度非常大可能會(huì)退化成鏈表。上圖中能看出來(lái)第一個(gè)樹(shù)的深度是 3，也就是說(shuō)最多只需 3 次比較，就可以找到節(jié)點(diǎn)，而第二個(gè)樹(shù)的深度是 7，最多需要 7 次比較才能找到節(jié)點(diǎn)。

圖中的右邊也屬于二分查找樹(shù)，但是性能方面已經(jīng)退化成了鏈表，查找數(shù)據(jù)的時(shí)間復(fù)雜度變成了 O(n)。這個(gè)問(wèn)題怎么解決呢?，人們提出了平衡二叉搜索樹(shù)(AVL 樹(shù))，它在二分搜索樹(shù)的基礎(chǔ)上增加了約束，保證每個(gè)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的高度差不能超過(guò) 1，也就是說(shuō)節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)仍然為平衡二叉樹(shù)。

這里說(shuō)一下，常見(jiàn)的平衡二叉樹(shù)有很多種，包括了平衡二叉搜索樹(shù)、紅黑樹(shù)、數(shù)堆、伸展樹(shù)。平衡二叉搜索樹(shù)是最早提出來(lái)的自平衡二叉搜索樹(shù)，當(dāng)我們提到平衡二叉樹(shù)時(shí)一般指的就是平衡二叉搜索樹(shù)。事實(shí)上，第一棵樹(shù)就屬于平衡二叉搜索樹(shù)，搜索時(shí)間復(fù)雜度就是 O(log2n)。

上文中我們提到過(guò)查詢時(shí)間的多少主要取決于硬盤(pán)的I/O操作，如果我們采用二叉樹(shù)的形式，即使通過(guò)平衡二叉搜索樹(shù)進(jìn)行了改良，樹(shù)的深度也是 O(log2n)，當(dāng) n 比較大時(shí)，深度也是比較高的，比如下圖的情況：

每訪問(wèn)一次節(jié)點(diǎn)就需要進(jìn)行一次磁盤(pán) I/O 操作，對(duì)于上面的樹(shù)來(lái)說(shuō)，我們需要進(jìn)行 5 次 I/O 操作。雖然平衡二叉樹(shù)比較的效率高，但是樹(shù)的深度也同樣高，這就意味著磁盤(pán) I/O 操作次數(shù)多，會(huì)影響整體數(shù)據(jù)查詢的效率。

再看看什么是 B 樹(shù)

在上文中，我們知道了如果二叉樹(shù)作為索引會(huì)導(dǎo)致樹(shù)變的很高，增加硬盤(pán)的 I/O 次數(shù)，影響數(shù)據(jù)查詢的時(shí)間。B 樹(shù)的出現(xiàn)就是為了解決這個(gè)問(wèn)題，B 樹(shù)的英文是 Balance Tree，也就是平衡的多路搜索樹(shù)，它的高度遠(yuǎn)小于平衡二叉樹(shù)的高度。在文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)中的索引結(jié)構(gòu)經(jīng)常采用 B 樹(shù)來(lái)實(shí)現(xiàn)。

我們來(lái)看看B樹(shù)結(jié)構(gòu)示意圖，如下圖所示：

B 樹(shù)作為平衡的多路搜索樹(shù)，它的每一個(gè)節(jié)點(diǎn)最多可以包括 M 個(gè)子節(jié)點(diǎn)，M 稱為 B 樹(shù)的階。在圖中你可以看到，每個(gè)磁盤(pán)塊中包括了關(guān)鍵字和子節(jié)點(diǎn)的指針。如果一個(gè)磁盤(pán)塊中包括了 x 個(gè)關(guān)鍵字，那么指針數(shù)就是 x+1。對(duì)于一個(gè) 100 階的 B 樹(shù)來(lái)說(shuō)，如果有 3 層的話最多可以存儲(chǔ)約 100 萬(wàn)的索引數(shù)據(jù)。對(duì)于大量的索引數(shù)據(jù)來(lái)說(shuō)，采用 B 樹(shù)的結(jié)構(gòu)是非常適合的，因?yàn)闃?shù)的高度要遠(yuǎn)小于二叉樹(shù)的高度。

結(jié)合B樹(shù)結(jié)構(gòu)示意圖，我們來(lái)一起看看B樹(shù)是如何進(jìn)行搜索的，假設(shè)我們想要查找的關(guān)鍵字是 9，那么步驟可以分為以下幾步：

• 我們與根節(jié)點(diǎn)的關(guān)鍵字 (17，35)進(jìn)行比較，9 小于 17 那么得到指針 P1;
• 按照指針 P1 找到磁盤(pán)塊 2，關(guān)鍵字為(8，12)，因?yàn)?9 在 8 和 12 之間，所以我們得到指針 P2;
• 按照指針 P2 找到磁盤(pán)塊 6，關(guān)鍵字為(9，10)，然后我們找到了關(guān)鍵字 9。

你能看出來(lái)在 B 樹(shù)的搜索過(guò)程中，我們比較的次數(shù)并不少，但如果把數(shù)據(jù)讀取出來(lái)然后在內(nèi)存中進(jìn)行比較，這個(gè)時(shí)間就是可以忽略不計(jì)的。而讀取磁盤(pán)塊本身需要進(jìn)行 I/O 操作，消耗的時(shí)間比在內(nèi)存中進(jìn)行比較所需要的時(shí)間要多，是數(shù)據(jù)查找用時(shí)的重要因素，B 樹(shù)相比于平衡二叉樹(shù)來(lái)說(shuō)磁盤(pán) I/O 操作要少，在數(shù)據(jù)查詢中比平衡二叉樹(shù)效率要高。

B樹(shù)Plus(B+ 樹(shù))

1. B+ 樹(shù)是基于B 樹(shù)改良過(guò)來(lái)的，目前主流的數(shù)據(jù)庫(kù)都支持B+ 樹(shù)作為索引方式，我們以MySQL為例，對(duì)比一下B+ 樹(shù)和B樹(shù)有哪些區(qū)別：
2. B+ 樹(shù)中，有 k 個(gè)孩子的節(jié)點(diǎn)就有 k 個(gè)關(guān)鍵字。也就是孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù)，而 B 樹(shù)中，孩子數(shù)量 = 關(guān)鍵字?jǐn)?shù) +1。
3. 非葉子節(jié)點(diǎn)的關(guān)鍵字也會(huì)同時(shí)存在在子節(jié)點(diǎn)中，并且是在子節(jié)點(diǎn)中所有關(guān)鍵字的最大(或最小)。
4. B+ 樹(shù)中，非葉子節(jié)點(diǎn)僅用于索引，不保存數(shù)據(jù)記錄，跟記錄有關(guān)的信息都放在葉子節(jié)點(diǎn)中。而 B 樹(shù)中，非葉子節(jié)點(diǎn)既保存索引，也保存數(shù)據(jù)記錄。

所有關(guān)鍵字都在葉子節(jié)點(diǎn)出現(xiàn)，葉子節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，而且葉子節(jié)點(diǎn)本身按照關(guān)鍵字的大小從小到大順序鏈接。

下圖就是一棵 B+ 樹(shù)，階數(shù)為 3，根節(jié)點(diǎn)中的關(guān)鍵字 1、18、35 分別是子節(jié)點(diǎn)(1，8，14)，(18，24，31)和(35，41，53)中的最小值。每一層父節(jié)點(diǎn)的關(guān)鍵字都會(huì)出現(xiàn)在下一層的子節(jié)點(diǎn)的關(guān)鍵字中，因此在葉子節(jié)點(diǎn)中包括了所有的關(guān)鍵字信息，并且每一個(gè)葉子節(jié)點(diǎn)都有一個(gè)指向下一個(gè)節(jié)點(diǎn)的指針，這樣就形成了一個(gè)鏈表。

比如，我們想要查找關(guān)鍵字 16，B+ 樹(shù)會(huì)自頂向下逐層進(jìn)行查找：

1. 與根節(jié)點(diǎn)的關(guān)鍵字 (1，18，35) 進(jìn)行比較，16 在 1 和 18 之間，得到指針 P1(指向磁盤(pán)塊 2)
2. 找到磁盤(pán)塊 2，關(guān)鍵字為(1，8，14)，因?yàn)?16 大于 14，所以得到指針 P3(指向磁盤(pán)塊 7)
3. 找到磁盤(pán)塊 7，關(guān)鍵字為(14，16，17)，然后我們找到了關(guān)鍵字 16，所以可以找到關(guān)鍵字 16 所對(duì)應(yīng)的數(shù)據(jù)。

整個(gè)過(guò)程一共進(jìn)行了 3 次 I/O 操作，看起來(lái) B+ 樹(shù)和 B 樹(shù)的查詢過(guò)程差不多，但是 B+ 樹(shù)和 B 樹(shù)有個(gè)根本的差異在于，B+ 樹(shù)的中間節(jié)點(diǎn)并不直接存儲(chǔ)數(shù)據(jù)。這樣的好處都有什么呢?

首先，B+ 樹(shù)查詢效率更穩(wěn)定。因?yàn)?B+ 樹(shù)每次只有訪問(wèn)到葉子節(jié)點(diǎn)才能找到對(duì)應(yīng)的數(shù)據(jù)，而在 B 樹(shù)中，非葉子節(jié)點(diǎn)也會(huì)存儲(chǔ)數(shù)據(jù)，這樣就會(huì)造成查詢效率不穩(wěn)定的情況，有時(shí)候訪問(wèn)到了非葉子節(jié)點(diǎn)就可以找到關(guān)鍵字，而有時(shí)需要訪問(wèn)到葉子節(jié)點(diǎn)才能找到關(guān)鍵字。

其次，B+ 樹(shù)的查詢效率更高，這是因?yàn)橥ǔ?B+ 樹(shù)比 B 樹(shù)更矮胖(階數(shù)更大，深度更低)，查詢所需要的磁盤(pán) I/O 也會(huì)更少。同樣的磁盤(pán)頁(yè)大小，B+ 樹(shù)可以存儲(chǔ)更多的節(jié)點(diǎn)關(guān)鍵字。

不僅是對(duì)單個(gè)關(guān)鍵字的查詢上，在查詢范圍上，B+ 樹(shù)的效率也比 B 樹(shù)高。這是因?yàn)樗嘘P(guān)鍵字都出現(xiàn)在 B+ 樹(shù)的葉子節(jié)點(diǎn)中，并通過(guò)有序鏈表進(jìn)行了鏈接。而在 B 樹(shù)中則需要通過(guò)中序遍歷才能完成查詢范圍的查找，效率要低很多。

總結(jié)

磁盤(pán)的 I/O 操作次數(shù)對(duì)索引的使用效率至關(guān)重要。雖然傳統(tǒng)的二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)查找數(shù)據(jù)的效率高，但很容易增加磁盤(pán) I/O 操作的次數(shù)，影響索引使用的效率。因此在構(gòu)造索引的時(shí)候，我們更傾向于采用“矮胖”的數(shù)據(jù)結(jié)構(gòu)。

B 樹(shù)和 B+ 樹(shù)都可以作為索引的數(shù)據(jù)結(jié)構(gòu)，在 MySQL 中采用的是 B+ 樹(shù)，B+ 樹(shù)在查詢性能上更穩(wěn)定，在磁盤(pán)頁(yè)大小相同的情況下，樹(shù)的構(gòu)造更加矮胖，所需要進(jìn)行的磁盤(pán) I/O 次數(shù)更少，更適合進(jìn)行關(guān)鍵字的范圍查詢。