前言

大家好，我是阿星。

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

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

索引

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

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

二叉搜索樹

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

我們先從最基本的二叉搜索樹說起。

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

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

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

N叉搜索樹

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

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

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

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

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

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

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

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

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

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

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

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