引言

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

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

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

最簡單的存儲引擎必須實現(xiàn)以下三個方法：

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

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

對于開發(fā)項目來說，能使用最簡單的數(shù)據(jù)結(jié)構(gòu)完成項目是非常棒的，這意味著更少的 bug 和更少的時間。

有序數(shù)組

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

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

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

哈希表

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

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

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

二叉平衡樹

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

綜上所屬，二叉平衡樹是可以用來做存儲引擎的，但有一定的局限性。

要素分析

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

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

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

通常來說，良好的計算機程序需要良好的局部性，局部性主要有：

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

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

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

那是不是局部性越高越好呢？不是這樣的。一方面局部性高會占用較高的內(nèi)存。另一方面，局部性過高會導(dǎo)致 write 方法變慢，因為局部性高了，write 方法需要移動的數(shù)據(jù)也就多了。

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

• 對于有序數(shù)組來說，通過拆分數(shù)組，使得在 write 方法的成本大大減少
• 對于平衡二叉樹來說，通過節(jié)點替換，大大增加了局部性，讓 scan 方法性能成本大大減少

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

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

最新評論