前面的幾篇文章已經(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 計(jì)算時(shí)的臨時(shí)數(shù)據(jù)結(jié)構(gòu)。

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

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

Hash Table 概念

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

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

Hash 函數(shù)

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

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

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

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

數(shù)據(jù)庫中常見的哈希函數(shù)實(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)哈希的實(shí)現(xiàn)方式，所謂靜態(tài)，一般是指哈希表的容量大小是固定的，所以能夠存儲(chǔ)數(shù)據(jù)的上限也是確定的，實(shí)際使用并不多，可以做參考。

Linear Probe Hash

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

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

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

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

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

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

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

這種方式比較簡單直觀，另一種方式是重復(fù)存儲(chǔ)，把每個(gè) key 都當(dāng)做是獨(dú)立的，插入方式和上面描述的完全一致。

Robin Hood Hash

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

它會(huì)記錄每個(gè) key 與其原始 hash 映射的位置的距離，例如下圖中的 A，因?yàn)椴迦肭皼]有任何數(shù)據(jù)，不存在哈希沖突，所以 A 記錄的距離是 0。

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

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

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

Cuckoo Hash

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

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

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

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

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

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

Dynamic Hash Scheme

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

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

Chained Hash

鏈?zhǔn)焦⒁粋€(gè)哈希表通過多個(gè) bucket 來維護(hù)，如果出現(xiàn)了哈希沖突，則將相同的 key 放到同一個(gè) bucket 中，如果 bucket 超過了規(guī)定的容量，則以鏈表串聯(lián)起一個(gè)新的 bucket。

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

Extendible Hash

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

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

例如上面的例子，第一個(gè) bucket 的 counter 是 1 ，當(dāng) key 定位到該 bucket 的時(shí)候，需要取 key 的前一位。而 bucket 2 和 3 的 counter 都是 2，需要取二進(jìn)制的前兩位。

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

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

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

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

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

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

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

Linear Hash

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

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

Conclusion

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

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