前言

大家好，我是阿星。

本文就接上一篇文章【??InnoDB原理篇：聊聊數(shù)據(jù)頁(yè)變成索引這件事??】來(lái)聊聊索引。

建議看完上篇文章再看本篇，食用效果最佳。

索引

假設(shè)給你一本非常厚的《Java編程思想》閱讀，沒(méi)有目錄，你想快速找到某一個(gè)章節(jié)的知識(shí)點(diǎn)，那估計(jì)得找一會(huì)了，如果有目錄就不一樣。

索引其實(shí)就是為了提高數(shù)據(jù)查詢(xún)的效率，就像書(shū)的目錄一樣，對(duì)于數(shù)據(jù)庫(kù)的表而言，索引其實(shí)就是它的目錄。

二叉搜索樹(shù)

索引的實(shí)現(xiàn)種類(lèi)繁多，比如常見(jiàn)的有序數(shù)組、哈希表、樹(shù)等，不同的結(jié)構(gòu)都有自己的適用場(chǎng)景和局限性，在數(shù)據(jù)庫(kù)領(lǐng)域中，樹(shù)結(jié)構(gòu)是被廣泛使用。

我們先從最基本的二叉搜索樹(shù)說(shuō)起。

二叉搜索樹(shù)的特點(diǎn)是：父節(jié)點(diǎn)左子樹(shù)所有結(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值，右子樹(shù)所有結(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值，如下圖所示：

如果要查id=4的數(shù)據(jù)，按照?qǐng)D中的搜索順序是索引頁(yè)A -> 索引頁(yè)B -> 索引頁(yè)D -> 數(shù)據(jù)頁(yè)0，時(shí)間復(fù)雜度是O(log(N))。

也就是說(shuō)，搜索速度與高度有關(guān)，樹(shù)越高，性能越差，假設(shè)100萬(wàn)行的表，使用二叉樹(shù)來(lái)存儲(chǔ)，樹(shù)高20，磁盤(pán)每次隨機(jī)讀一個(gè)數(shù)據(jù)塊需要10ms左右，單獨(dú)訪(fǎng)問(wèn)一個(gè)行可能需要20個(gè)10ms的時(shí)間，這個(gè)查詢(xún)可真夠慢的。

N叉搜索樹(shù)

為了減少磁盤(pán)隨機(jī)讀IO，就必須控制好樹(shù)的高度，那就不應(yīng)該使用二叉樹(shù)，而是使用N叉樹(shù)，這里的N代表數(shù)據(jù)塊的大小。

也就說(shuō)，你一個(gè)索引頁(yè)存儲(chǔ)的數(shù)據(jù)越多，樹(shù)會(huì)越矮，InnoDB中就使用了B+樹(shù)來(lái)實(shí)現(xiàn)索引。

以InnoDB的整數(shù)字段建立索引為例。

一個(gè)頁(yè)默認(rèn)16kb,整數(shù)(bigint)字段的長(zhǎng)度為8B，另外還跟著6B的指向其子樹(shù)的指針，這意味著一個(gè)索引頁(yè)可以存儲(chǔ)接近1200條數(shù)據(jù)(16kb/14B ≈ 1170)。

如果這顆B+樹(shù)高度為4，就可以存1200的3次方的值，差不多17億條數(shù)據(jù)。

考慮到樹(shù)根節(jié)點(diǎn)總是在內(nèi)存中的，樹(shù)的第二層很大概率也在內(nèi)存中，所以一次搜索最多只需要訪(fǎng)問(wèn)2次磁盤(pán)IO。

可能小伙伴會(huì)有疑問(wèn)，為什么樹(shù)的根節(jié)點(diǎn)與樹(shù)的第二層會(huì)在內(nèi)存，第三層、第四層卻沒(méi)在?

道理很簡(jiǎn)單，看下數(shù)據(jù)大小就清楚了。

• 樹(shù)的根節(jié)點(diǎn)就是16kb的索引頁(yè)，內(nèi)存完全可以放下，里面存儲(chǔ)1200條索引目錄
• 樹(shù)的第二層總共是1200個(gè)索引頁(yè)，1200 * 16KB = 20M內(nèi)存依然放得下的
• 樹(shù)的第三層1200 * 1200 = 144w頁(yè)，144w * 16kB = 23G放內(nèi)存就不合適了
• 樹(shù)的第四層就是數(shù)據(jù)頁(yè)了，屬于完整數(shù)據(jù)了，更不可能全部加載進(jìn)內(nèi)存了

最后再感受下索引搜索的流程。

假設(shè)1億數(shù)據(jù)量的表，根據(jù)主鍵id建立了B+樹(shù)索引，現(xiàn)在搜索id=2699的數(shù)據(jù)，流程如下：

• 內(nèi)存中直接獲取樹(shù)根索引頁(yè)，對(duì)樹(shù)根索引頁(yè)內(nèi)的目錄進(jìn)行二分查找，定位到第二層的索引頁(yè)
• 內(nèi)存中直接獲取第二層的索引頁(yè)，對(duì)索引頁(yè)內(nèi)的目錄進(jìn)行二分查找，定位到第三層的索引頁(yè)
• 從磁盤(pán)加載第三層的索引頁(yè)到內(nèi)存中，對(duì)索引頁(yè)內(nèi)的目錄進(jìn)行二分查找，定位到第四層數(shù)據(jù)頁(yè)
• 從磁盤(pán)加載第四層的數(shù)據(jù)頁(yè)到內(nèi)存中，數(shù)據(jù)頁(yè)變成緩存頁(yè)，對(duì)緩存頁(yè)中的目錄進(jìn)行二分查找，定位到具體的行數(shù)據(jù)