前面的幾篇文章已經將磁盤管理和內存 buffer pool 管理的內容都介紹完了，接下來繼續向上一層，來介紹關于 access method 的內容。

access method 主要是介紹一些數據結構，例如 Hash Table 和 Tree。這些數據結構可以用來做表的索引，以及一些在 sql 計算時的臨時數據結構。

在設計和使用這些數據結構時，需要注意兩個問題，一是數據的組織，怎樣將數據組織在內存或者磁盤中，并且能夠高效的訪問；二是數據結構的并發訪問問題，需要保證其在多線程環境下的數據安全。

今天先來看一下在數據庫里面頻繁被使用，以及數據結構中也會經常涉及到的哈希表。

Hash Table 概念

Hash Table 是一個無序的 key 到 value 的映射實現，它使用一個哈希函數計算數據存儲到數組中（槽位）的位置，并且平均情況下，能夠在 O(1) 的時間內訪問元素。

如下圖所示，我們通過一個 hash 函數，計算 key 在數組中中的下標，然后 key 對應了具體的 value。當查找數據時，也需要計算哈希值，然后定位到 key 所在的位置進行取值。

Hash 函數

從前面的描述中可以看到，哈希函數在 Hash Table 中的作用至關重要。

哈希函數可以將任意類型的 key 轉換為一個代表這個 key 的整數，在理想的情況下，我們希望任意不同的 key 經過哈希函數計算出來的值都是不同的，但在實際的哈希函數實現中，這幾乎是不太可能的。

如果不同的 key 通過哈希函數計算出來的值是一樣的，這種情況叫做哈希沖突（conflict），又叫哈希碰撞（collision）。

一般來說，計算哈希的速度越快，哈希沖突的概率越大，反之則越低，這就需要在實際設計時進行權衡。

數據庫中常見的哈希函數實現有下列這幾種：

• crc64：https://create.stephan-brumme.com/crc32/
• MurmurHash：https://github.com/aappleby/smhasher
• Google CityHash：https://github.com/google/cityhash
• Facebook XXHash：http://cyan4973.github.io/xxHash/
• Google FarmHash：https://github.com/google/farmhash

Static Hash Scheme

接下來了解一下幾種靜態哈希的實現方式，所謂靜態，一般是指哈希表的容量大小是固定的，所以能夠存儲數據的上限也是確定的，實際使用并不多，可以做參考。

Linear Probe Hash

線性探測（Linear Probe）是一種比較直觀簡潔的 Hash Table 實現方式了。

其基本思路是如果映射之后的 key 存儲的位置已經被占用了，那么它會依次遍歷數組，直到找到一個空閑的位置插入數據。

如下，新插入的數據 E 通過計算后，其位置在 A 的位置。

但是 A 處已經有數據了，此時發生了沖突，所以會向后遍歷，然后找到 D 之后的空閑位置插入。

刪除的邏輯比較類似，也是通過哈希函數計算 key 的位置，然后找到對應的數據并刪除。如果 key 并不在原來的位置上，那么需要像插入一樣遍歷，直到找到目標 key。

刪除一般有兩種做法，一是直接在刪除的位置設置一個墓碑值，表示其已被刪除，二是移動其他的元素來填充刪除的位置，這種方式并不常用。

重復 key哈希表中對于重復的 key 的處理方式一般有兩種，一是通過一個 value 鏈表的方式，將同一個 key 的多個元素串聯起來。

這種方式比較簡單直觀，另一種方式是重復存儲，把每個 key 都當做是獨立的，插入方式和上面描述的完全一致。

Robin Hood Hash

robin hood 哈希類似于線性探測，并有一定的改進。

它會記錄每個 key 與其原始 hash 映射的位置的距離，例如下圖中的 A，因為插入前沒有任何數據，不存在哈希沖突，所以 A 記錄的距離是 0。

如果此時插入數據 C，如果 C 映射的位置也是 A，這樣就產生了哈希沖突，于是向下探測一位，將 C 插到 A 之后的位置，這時候 C 與其原始映射位置的距離就是 1。

當又有新的 key 插入時，如果產生了沖突，那么繼續向后探測，并且比較映射距離的值，如果新插入的 key 的距離大于該位置的值，則將新的 key 插入。

例如上面的這個例子，如果新插入的 E 映射到了 A 的位置，此時 E 的距離是 0，和 A 的距離相等，繼續向下，此時 E 的距離是 1，和 C 相等，又繼續，此時 E 變為 2，大于了 D 的距離 1，于是將 E 插入到 D 的位置，并且將 D 挪到到下一個空閑的位置。

Cuckoo Hash

cuckoo hash 使用多個哈希表，并且每個哈希表使用一個不同 seed （隨機種子）的哈希函數。當插入數據時，對 key 輪流用每個哈希函數都計算哈希值，如果對應的哈希表有空閑空間，則直接插入。

例如下面的例子，使用了兩個哈希表，插入 key A 的時候，計算兩個哈希值，并且查詢到第一個哈希表有空閑，則直接將數據插入到哈希表 1 中。

如果此時在插入一條數據 B，如果在哈希表 1 中有沖突，但是在哈希表 2 中沒有沖突，則將數據插入到哈希表 2 中。

如果此時再插入一個 key C，經過哈希函數計算后，發現它和兩個哈希表都有沖突。

這時候需要選擇一個哈希表，將其中的 key 先拿出來，騰一個位置給 C，例如可以將 C 插入到 A 的位置。然后對 A 再計算哈希值，如果 A 在哈希表 2 中沒有沖突，則直接將 A 插入到哈希表 2 中。

cuckoo hash 在 Github 上也有對應的一些實現：https://github.com/efficient/libcuckoo

Dynamic Hash Scheme

前面提到的這幾種哈希表的實現方式，都可以認為是靜態的，即哈希表中能存儲多少數據，是一開始就確定下來的，并不會涉及到擴容。

但實際環境中，我們大多數時候都希望哈希表是可以隨著數據量的增長而擴張的，下面再介紹幾種更常用的，可以自動動態擴容的哈希表實現。

Chained Hash

鏈式哈希將一個哈希表通過多個 bucket 來維護，如果出現了哈希沖突，則將相同的 key 放到同一個 bucket 中，如果 bucket 超過了規定的容量，則以鏈表串聯起一個新的 bucket。

每個 bucket 一般會有一個指針，標識其位置，當一個 key 經過 hash 之后，可以通過這個指針找到它所屬的 bucket。

Extendible Hash

extendible hash（可擴展哈希）和 chained hash 比較類似，都使用到了bucket 這個概念，同時也會有一個執行 bucket 的指針數組。

與之不同的是，extendible hash 將 key 計算哈希值后，會將其值轉換為一個二進制表示，然后它會維護一個 global counter，記錄定位到 bucket 指針數組，需要取 key 的二進制的多少位；每個 bucket 也有一個 counter，記為 local counter，表示的是定位到該 bucket 需要二進制的多少位。

例如上面的例子，第一個 bucket 的 counter 是 1 ，當 key 定位到該 bucket 的時候，需要取 key 的前一位。而 bucket 2 和 3 的 counter 都是 2，需要取二進制的前兩位。

如果需要查詢數據，先對 key 計算哈希值，例如下圖中的 A，計算其哈希值后，global counter 是 2，所以只需要取前兩位即可，然后通過 bucket 的指針獲取到 bucket 的位置，遍歷其中的數據進行查找。

如果需要新插入數據，則和查找的過程類似，同樣計算哈希值，然后找到對應的 bucket，將數據放到 bucket 的空閑位置即可。

如果對應的 bucket 沒有空閑的位置了，這時候需要進行 split 分裂操作。

首先將 global counter 的值增加 1，然后新建一個 bucket，將舊的對應的那個 bucket 的 counter 也增加 1，并且讓新的 bucket 的 counter 等于這個值。然后重新通過這個 key 的二進制位來移動舊的 bucket 中的數據。

例如下面的例子，需要插入 key C，但是它所映射的 bucket 已經滿了。

此時將 global counter 增加為 3，并且新增一個 bucket，counter 為舊的值加一，也為 3。然后將舊的那個 bucket 按照新的進制位重新存放，此時 bucket 中就有空閑的位置了。

更詳細內容可以參考：https://zhuanlan.zhihu.com/p/375039823

Linear Hash

前面提到的 extendible hash 在分裂的時候，需要擴展 bucket 指針數組（又叫 slot array），這時候一般需要對哈希表加全局鎖，以防止并發讀寫沖突。但是這樣鎖的粒度較大，容易造成哈希表的讀寫瓶頸。

另一種 linear hash 會維護一個分裂指針 split pointer，當有任意的 bucket 分裂時，split pointer 指向的 bucket 也會分裂。這種方式介紹不多，實際使用應該也較少，就不詳細介紹了。

Conclusion

哈希表是一個高效的數據結構，大多時候能夠在 O(1) 的情況下插入和查詢數據，在數據庫系統中，有很多地方都使用到了哈希表，例如前面提到的 page table，page directory，以及執行 sql 查詢時一些用于 join 的臨時數據結構。

但是哈希表的應用場景也有限，因為它存儲的所有 key 都是無序的，這樣雖然適合點查，但是無法進行范圍掃描，在更加通用的場景下，數據庫中的表索引使用最廣泛的還是 B+ 樹。