前面的幾篇文章已經(jīng)將磁盤管理和內(nèi)存 buffer pool 管理的內(nèi)容都介紹完了，接下來繼續(xù)向上一層，來介紹關(guān)于 access method 的內(nèi)容。

access method 主要是介紹一些數(shù)據(jù)結(jié)構(gòu)，例如 Hash Table 和 Tree。這些數(shù)據(jù)結(jié)構(gòu)可以用來做表的索引，以及一些在 sql 計算時的臨時數(shù)據(jù)結(jié)構(gòu)。

在設(shè)計和使用這些數(shù)據(jù)結(jié)構(gòu)時，需要注意兩個問題，一是數(shù)據(jù)的組織，怎樣將數(shù)據(jù)組織在內(nèi)存或者磁盤中，并且能夠高效的訪問；二是數(shù)據(jù)結(jié)構(gòu)的并發(fā)訪問問題，需要保證其在多線程環(huán)境下的數(shù)據(jù)安全。

今天先來看一下在數(shù)據(jù)庫里面頻繁被使用，以及數(shù)據(jù)結(jié)構(gòu)中也會經(jīng)常涉及到的哈希表。

Hash Table 概念

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

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

Hash 函數(shù)

從前面的描述中可以看到，哈希函數(shù)在 Hash Table 中的作用至關(guān)重要。

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

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

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

數(shù)據(jù)庫中常見的哈希函數(shù)實現(xiàn)有下列這幾種：

• 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

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

Linear Probe Hash

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

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

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

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

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

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

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

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

Robin Hood Hash

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

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

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

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

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

Cuckoo Hash

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

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

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

如果此時再插入一個 key C，經(jīng)過哈希函數(shù)計算后，發(fā)現(xiàn)它和兩個哈希表都有沖突。

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

cuckoo hash 在 Github 上也有對應(yīng)的一些實現(xiàn)：https://github.com/efficient/libcuckoo

Dynamic Hash Scheme

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

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

Chained Hash

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

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

Extendible Hash

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

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

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

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

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

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

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

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

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

更詳細內(nèi)容可以參考：https://zhuanlan.zhihu.com/p/375039823

Linear Hash

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

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

Conclusion

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

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