建站
咨詢
售后
建站咨詢
新聞中心
前面的幾篇文章已經(jīng)將磁盤管理和內(nèi)存 buffer pool 管理的內(nèi)容都介紹完了，接下來繼續(xù)向上一層，來介紹關(guān)于 access method 的內(nèi)容。
成都創(chuàng)新互聯(lián)專注于長壽網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗。 熱誠為您提供長壽營銷型網(wǎng)站建設(shè)，長壽網(wǎng)站制作、長壽網(wǎng)頁設(shè)計、長壽網(wǎng)站官網(wǎng)定制、成都小程序開發(fā)服務(wù)，打造長壽網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供長壽網(wǎng)站排名全網(wǎng)營銷落地服務(wù)。
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ù)組中中的下標(biāo)，然后 key 對應(yīng)了具體的 value。當(dāng)查找數(shù)據(jù)時，也需要計算哈希值，然后定位到 key 所在的位置進(jìn)行取值。
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è)計時進(jìn)行權(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 并不在原來的位置上，那么需要像插入一樣遍歷，直到找到目標(biāo) key。
刪除一般有兩種做法，一是直接在刪除的位置設(shè)置一個墓碑值，表示其已被刪除，二是移動其他的元素來填充刪除的位置，這種方式并不常用。
重復(fù) key哈希表中對于重復(fù)的 key 的處理方式一般有兩種，一是通過一個 value 鏈表的方式，將同一個 key 的多個元素串聯(lián)起來。
這種方式比較簡單直觀，另一種方式是重復(fù)存儲，把每個 key 都當(dāng)做是獨立的，插入方式和上面描述的完全一致。
Robin Hood Hash
robin hood 哈希類似于線性探測，并有一定的改進(jìn)。
它會記錄每個 key 與其原始 hash 映射的位置的距離，例如下圖中的 A，因為插入前沒有任何數(shù)據(jù)，不存在哈希沖突，所以 A 記錄的距離是 0。
如果此時插入數(shù)據(jù) C，如果 C 映射的位置也是 A，這樣就產(chǎn)生了哈希沖突，于是向下探測一位，將 C 插到 A 之后的位置，這時候 C 與其原始映射位置的距離就是 1。
當(dāng)又有新的 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 （隨機(jī)種子）的哈希函數(shù)。當(dāng)插入數(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)方式，都可以認(rèn)為是靜態(tài)的，即哈希表中能存儲多少數(shù)據(jù)，是一開始就確定下來的，并不會涉及到擴(kuò)容。
但實際環(huán)境中，我們大多數(shù)時候都希望哈希表是可以隨著數(shù)據(jù)量的增長而擴(kuò)張的，下面再介紹幾種更常用的，可以自動動態(tài)擴(kuò)容的哈希表實現(xiàn)。
Chained Hash
鏈?zhǔn)焦⒁粋€哈希表通過多個 bucket 來維護(hù)，如果出現(xiàn)了哈希沖突，則將相同的 key 放到同一個 bucket 中，如果 bucket 超過了規(guī)定的容量，則以鏈表串聯(lián)起一個新的 bucket。
每個 bucket 一般會有一個指針，標(biāo)識其位置，當(dāng)一個 key 經(jīng)過 hash 之后，可以通過這個指針找到它所屬的 bucket。
Extendible Hash
extendible hash（可擴(kuò)展哈希）和 chained hash 比較類似，都使用到了bucket 這個概念，同時也會有一個執(zhí)行 bucket 的指針數(shù)組。
與之不同的是，extendible hash 將 key 計算哈希值后，會將其值轉(zhuǎn)換為一個二進(jìn)制表示，然后它會維護(hù)一個 global counter，記錄定位到 bucket 指針數(shù)組，需要取 key 的二進(jìn)制的多少位；每個 bucket 也有一個 counter，記為 local counter，表示的是定位到該 bucket 需要二進(jìn)制的多少位。
例如上面的例子，第一個 bucket 的 counter 是 1 ，當(dāng) key 定位到該 bucket 的時候，需要取 key 的前一位。而 bucket 2 和 3 的 counter 都是 2，需要取二進(jìn)制的前兩位。
如果需要查詢數(shù)據(jù)，先對 key 計算哈希值，例如下圖中的 A，計算其哈希值后，global counter 是 2，所以只需要取前兩位即可，然后通過 bucket 的指針獲取到 bucket 的位置，遍歷其中的數(shù)據(jù)進(jìn)行查找。
如果需要新插入數(shù)據(jù)，則和查找的過程類似，同樣計算哈希值，然后找到對應(yīng)的 bucket，將數(shù)據(jù)放到 bucket 的空閑位置即可。
如果對應(yīng)的 bucket 沒有空閑的位置了，這時候需要進(jìn)行 split 分裂操作。
首先將 global counter 的值增加 1，然后新建一個 bucket，將舊的對應(yīng)的那個 bucket 的 counter 也增加 1，并且讓新的 bucket 的 counter 等于這個值。然后重新通過這個 key 的二進(jìn)制位來移動舊的 bucket 中的數(shù)據(jù)。
例如下面的例子，需要插入 key C，但是它所映射的 bucket 已經(jīng)滿了。
此時將 global counter 增加為 3，并且新增一個 bucket，counter 為舊的值加一，也為 3。然后將舊的那個 bucket 按照新的進(jìn)制位重新存放，此時 bucket 中就有空閑的位置了。
更詳細(xì)內(nèi)容可以參考：https://zhuanlan.zhihu.com/p/375039823
Linear Hash
前面提到的 extendible hash 在分裂的時候，需要擴(kuò)展 bucket 指針數(shù)組（又叫 slot array），這時候一般需要對哈希表加全局鎖，以防止并發(fā)讀寫沖突。但是這樣鎖的粒度較大，容易造成哈希表的讀寫瓶頸。
另一種 linear hash 會維護(hù)一個分裂指針 split pointer，當(dāng)有任意的 bucket 分裂時，split pointer 指向的 bucket 也會分裂。這種方式介紹不多，實際使用應(yīng)該也較少，就不詳細(xì)介紹了。
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 都是無序的，這樣雖然適合點查，但是無法進(jìn)行范圍掃描，在更加通用的場景下，數(shù)據(jù)庫中的表索引使用最廣泛的還是 B+ 樹。
本文名稱：CMU 15445 學(xué)習(xí)之Hash Table
標(biāo)題鏈接：http://www.dlmjj.cn/article/cdcosdo.html
