眾所周知，MySQL 的 InnoDB 存儲引擎使用了 B+ 樹作為索引實現，那麼為什麼不使用其他的數據結構呢？數組、鏈表或者哈希表。實現存儲引擎究竟需要什麼條件呢？

我們現在先以存儲最簡單的數據為例，這裏的數據類似於 json 對象。有 key 和 value。

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

最簡單的存儲引擎必須實現以下三個方法：

• read: (key: number) => value 查找 key 並返回 value
• write: (key: number, value) => void 查找並插入 key 以及 value
• scan: (begin: number, end: number) => value[] 查找返回 key 範圍內數據

簡單數據結構

對於開發項目來説，能使用最簡單的數據結構完成項目是非常棒的，這意味着更少的 bug 和更少的時間。

有序數組

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

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

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

哈希表

不考慮空間是不可能的，那麼直接捨棄 scan 方法呢？在某些業務場景下是可以不使用 scan 方法的。

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

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

二叉平衡樹

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

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

要素分析

在分析上面幾種數據結構後，我們不難得出結論。

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

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

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

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

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

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

那是不是局部性越高越好呢？不是這樣的。一方面局部性高會佔用較高的內存。另一方面，局部性過高會導致 write 方法變慢，因為局部性高了，write 方法需要移動的數據也就多了。

平衡二叉樹是唯一能在現實世界中實現 3 個方法的數據結構，局部性是提升 scan 方法性能的必要條件。那麼把兩者結合呢？把平衡二叉樹的結點構造成一個個有序數組，這樣就可以得到兩個方案的優點了。

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

事實上，只要能夠低成本且高效的維持數據有序的數據結構都可以作為存儲引擎。無論是 B 樹, B+ 樹或者 跳錶。同時每個數據結構都有其對應的側重點。只要抓住這幾個點，就不難分析出為什麼當前存儲引擎使用該數據結構作為索引了。

鼓勵一下

如果你覺得這篇文章不錯，希望可以給與我一些鼓勵，在我的 github 博客下幫忙 star 一下。

博客地址