MySQL存儲引擎的實現(xiàn)要素分析

更新時間：2023年09月14日 14:13:01 作者：jump__jump

這篇文章主要為大家介紹了MySQL存儲引擎的實現(xiàn)要素分析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

引言

眾所周知，MySQL 的 InnoDB 存儲引擎使用了 B+ 樹作為索引實現(xiàn)，那么為什么不使用其他的數(shù)據(jù)結構呢？數(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ù)結構

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

有序數(shù)組

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

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

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

哈希表

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

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

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

二叉平衡樹

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

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