引言

眾所周知，MySQL 的 InnoDB 存儲(chǔ)引擎使用了 B+ 樹(shù)作為索引實(shí)現(xiàn)，那么為什么不使用其他的數(shù)據(jù)結(jié)構(gòu)呢？數(shù)組、鏈表或者哈希表。實(shí)現(xiàn)存儲(chǔ)引擎究竟需要什么條件呢？

我們現(xiàn)在先以存儲(chǔ)最簡(jiǎn)單的數(shù)據(jù)為例，這里的數(shù)據(jù)類(lèi)似于 json 對(duì)象。有 key 和 value。

{
    "0": "value1",
    "1": "value2" 
}

最簡(jiǎn)單的存儲(chǔ)引擎必須實(shí)現(xiàn)以下三個(gè)方法：

• read: (key: number) => value 查找 key 并返回 value
• write: (key: number, value) => void 查找并插入 key 以及 value
• scan: (begin: number, end: number) => value[] 查找返回 key 范圍內(nèi)數(shù)據(jù)

簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)

對(duì)于開(kāi)發(fā)項(xiàng)目來(lái)說(shuō)，能使用最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)完成項(xiàng)目是非常棒的，這意味著更少的 bug 和更少的時(shí)間。

有序數(shù)組

如果當(dāng)前有序數(shù)組的位置和存儲(chǔ)的 key 可以一一對(duì)應(yīng)的話(huà)，也就是數(shù)組 index 對(duì)應(yīng) key（沒(méi)有對(duì)應(yīng)也就是稀疏數(shù)組），我們的 read 和 write 方法的時(shí)間復(fù)雜度會(huì)是 O(1)，scan 方法也是 O(1)。但數(shù)據(jù)量稍大就扛不住了。

退而求其次，不存在位置對(duì)應(yīng)主鍵的情況下，有序數(shù)組緊密存儲(chǔ)，這樣可以通過(guò)二分查找，read 和 scan 方法的時(shí)間復(fù)雜度為 O(log2n)。但 write 方法成本會(huì)高到離譜。

綜上所屬，有序數(shù)組是在數(shù)據(jù)量少的情況下可以用來(lái)做存儲(chǔ)引擎的。

哈希表

不考慮空間是不可能的，那么直接舍棄 scan 方法呢？在某些業(yè)務(wù)場(chǎng)景下是可以不使用 scan 方法的。

哈希表使用一對(duì)多的組織方式來(lái)實(shí)現(xiàn) read 和 write。先對(duì) key 進(jìn)行 hash 運(yùn)算然后再尋址，性能基本接近于 O(1)。

綜上所屬，哈希表在不考慮 scan 方法的情況下是可以用來(lái)做存儲(chǔ)引擎的。

二叉平衡樹(shù)

二叉平衡樹(shù)相對(duì) hash 和有序數(shù)據(jù)來(lái)說(shuō)是一個(gè)折衷方案。該數(shù)據(jù)結(jié)構(gòu)是通過(guò)鏈表實(shí)現(xiàn)的，所以不需要大塊內(nèi)存。它的 read 和 write 都是 O(log2n)，雖然 scan 遍歷慢的難以忍受，但是它能夠?qū)崿F(xiàn)這三個(gè)方法了。

綜上所屬，二叉平衡樹(shù)是可以用來(lái)做存儲(chǔ)引擎的，但有一定的局限性。

要素分析

在分析上面幾種數(shù)據(jù)結(jié)構(gòu)后，我們不難得出結(jié)論。

• 有序性是實(shí)現(xiàn) scan 方法的前提條件
• 局部性是提升 scan/read 方法性能的必要條件

這里我們提到了局部性，那么局部性究竟是什么呢？

通常來(lái)說(shuō)，良好的計(jì)算機(jī)程序需要良好的局部性，局部性主要有：

• 時(shí)間局部性 ：指的是同一個(gè)內(nèi)存位置，從時(shí)間維度來(lái)看，它能夠在較短時(shí)間內(nèi)被多次引用
• 空間局部性 ：指的是同一個(gè)內(nèi)存位置，從空間維度來(lái)看，它附近的內(nèi)存位置能夠被引用

仔細(xì)分析一下，scan 方法和空間局部性有關(guān)。如果使用平衡二叉樹(shù)來(lái)作為查詢(xún)的數(shù)據(jù)結(jié)構(gòu)。scan 的性能是非常差的，但是使用有序數(shù)組來(lái)作為數(shù)據(jù)結(jié)構(gòu) scan 可以直接遍歷獲取兩者之間的數(shù)據(jù)，性能非常高。

同時(shí)，局部性也和 read 性能有很大關(guān)系。使用二分法來(lái)查詢(xún)數(shù)據(jù)。局部性較低的情況下，read 需要多次從磁盤(pán)加載數(shù)據(jù)。如果局部性高，直接一次加載數(shù)據(jù)即可。

那是不是局部性越高越好呢？不是這樣的。一方面局部性高會(huì)占用較高的內(nèi)存。另一方面，局部性過(guò)高會(huì)導(dǎo)致 write 方法變慢，因?yàn)榫植啃愿吡?，write 方法需要移動(dòng)的數(shù)據(jù)也就多了。

平衡二叉樹(shù)是唯一能在現(xiàn)實(shí)世界中實(shí)現(xiàn) 3 個(gè)方法的數(shù)據(jù)結(jié)構(gòu)，局部性是提升 scan 方法性能的必要條件。那么把兩者結(jié)合呢？把平衡二叉樹(shù)的結(jié)點(diǎn)構(gòu)造成一個(gè)個(gè)有序數(shù)組，這樣就可以得到兩個(gè)方案的優(yōu)點(diǎn)了。

• 對(duì)于有序數(shù)組來(lái)說(shuō)，通過(guò)拆分?jǐn)?shù)組，使得在 write 方法的成本大大減少
• 對(duì)于平衡二叉樹(shù)來(lái)說(shuō)，通過(guò)節(jié)點(diǎn)替換，大大增加了局部性，讓 scan 方法性能成本大大減少

事實(shí)上，只要能夠低成本且高效的維持?jǐn)?shù)據(jù)有序的數(shù)據(jù)結(jié)構(gòu)都可以作為存儲(chǔ)引擎。無(wú)論是 B 樹(shù), B+ 樹(shù)或者 跳表。同時(shí)每個(gè)數(shù)據(jù)結(jié)構(gòu)都有其對(duì)應(yīng)的側(cè)重點(diǎn)。只要抓住這幾個(gè)點(diǎn)，就不難分析出為什么當(dāng)前存儲(chǔ)引擎使用該數(shù)據(jù)結(jié)構(gòu)作為索引了。

以上就是MySQL存儲(chǔ)引擎的實(shí)現(xiàn)要素分析的詳細(xì)內(nèi)容，更多關(guān)于MySQL存儲(chǔ)引擎的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論