一、作為一個(gè)K-V數(shù)據(jù)庫(kù)，levelDB索引要使用LSM樹(shù)實(shí)現(xiàn)，而不采用哈希索引的原因

1、LSM樹(shù)有快速的寫(xiě)入性能

LSM樹(shù)的寫(xiě)入性能優(yōu)于哈希索引。哈希索引在插入數(shù)據(jù)時(shí)需要從鏈表中查找是否已經(jīng)存在相同的哈希值的鍵，而LSM樹(shù)的寫(xiě)入則是以順序的方式追加數(shù)據(jù)到磁盤(pán)中，并非順序?qū)懭氪疟P(pán)，而是寫(xiě)入到內(nèi)存緩存中。這種分層追加和緩存設(shè)計(jì)方式，使得LevelDB具有比哈希表更快的寫(xiě)入速度。

2、LSM樹(shù)有優(yōu)異的單機(jī)讀取性能

LSM樹(shù)在內(nèi)存中維護(hù)一個(gè)鏈表來(lái)加速讀取操作。LevelDB使用一個(gè)類似于Write Ahead Log（WAL）的技術(shù)，將每個(gè)寫(xiě)入操作都記錄到磁盤(pán)上，并在內(nèi)存中建立一份索引。使用內(nèi)存索引可以快速地查找這些寫(xiě)入記錄，而磁盤(pán)記錄則由后臺(tái)線程讀取。

3、LSM樹(shù)適合處理大量數(shù)據(jù)

LSM樹(shù)的分層設(shè)計(jì)也使得它能夠處理大量數(shù)據(jù)。LevelDB將磁盤(pán)上的數(shù)據(jù)分為多層，每層都存儲(chǔ)了一定范圍的鍵值對(duì)。較低層的數(shù)據(jù)范圍更廣，而較高層數(shù)據(jù)范圍較小。當(dāng)內(nèi)存中的鍵值對(duì)達(dá)到一定數(shù)量時(shí)，LevelDB會(huì)將它們寫(xiě)入到磁盤(pán)上的最低層。一段時(shí)間后，這些數(shù)據(jù)會(huì)被合并到更高層，形成新的磁盤(pán)文件。這個(gè)分層方式也使得在大多數(shù)情況下，讀取一個(gè)鍵的操作只需要讀取一個(gè)或少數(shù)幾個(gè)磁盤(pán)文件，而不是讀取整個(gè)數(shù)據(jù)庫(kù)。

4、LSM樹(shù)支持?jǐn)?shù)據(jù)范圍查詢

由于LSM樹(shù)采用了分層設(shè)計(jì)，因此LevelDB支持對(duì)某一層或多層的萃取搜索，或者查詢某個(gè)數(shù)據(jù)范圍內(nèi)的所有鍵值對(duì)，而哈希表只能支持對(duì)單個(gè)鍵值的搜索。

二、LSM樹(shù)介紹

1、簡(jiǎn)介

LSM樹(shù)（Log-Structured-Merge-Tree）的名字往往會(huì)給初識(shí)者一個(gè)錯(cuò)誤的印象，事實(shí)上，LSM樹(shù)并不像B+樹(shù)、紅黑樹(shù)一樣是一顆嚴(yán)格的樹(shù)狀數(shù)據(jù)結(jié)構(gòu)，它其實(shí)是一種存儲(chǔ)結(jié)構(gòu)，目前HBase，LevelDB，RocksDB這些NoSQL存儲(chǔ)都是采用的LSM樹(shù)。

LSM樹(shù)的核心特點(diǎn)是利用順序?qū)憗?lái)提高寫(xiě)性能，但因?yàn)榉謱樱ù颂幏謱邮侵傅姆譃閮?nèi)存和文件兩部分）的設(shè)計(jì)會(huì)稍微降低讀性能，但是通過(guò)犧牲小部分讀性能換來(lái)高性能寫(xiě)，使得LSM樹(shù)成為非常流行的存儲(chǔ)結(jié)構(gòu)。

2、誕生背景

傳統(tǒng)關(guān)系型數(shù)據(jù)庫(kù)使用btree或一些變體作為存儲(chǔ)結(jié)構(gòu)，能高效進(jìn)行查找。但保存在磁盤(pán)中時(shí)它也有一個(gè)明顯的缺陷，那就是邏輯上相離很近但物理卻可能相隔很遠(yuǎn)，這就可能造成大量的磁盤(pán)隨機(jī)讀寫(xiě)。隨機(jī)讀寫(xiě)比順序讀寫(xiě)慢很多，為了提升IO性能，我們需要一種能將隨機(jī)操作變?yōu)轫樞虿僮鞯臋C(jī)制，于是便有了LSM樹(shù)。LSM樹(shù)能讓我們進(jìn)行順序?qū)懘疟P(pán)，從而大幅提升寫(xiě)操作，作為代價(jià)的是犧牲了一些讀性能。

3、核心思想

LSM樹(shù)三個(gè)重要組成部分，分別是MemTable，Immutable MemTable和SSTable（Sorted String Table）。MemTable是在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，用于保存最近更新的數(shù)據(jù)，會(huì)按照Key有序地組織這些數(shù)據(jù)，LSM樹(shù)對(duì)于具體如何組織有序地組織數(shù)據(jù)并沒(méi)有明確的數(shù)據(jù)結(jié)構(gòu)定義，例如Hbase使跳躍表來(lái)保證內(nèi)存中key的有序。因?yàn)閿?shù)據(jù)暫時(shí)保存在內(nèi)存中，內(nèi)存并不是可靠存儲(chǔ)，如果斷電會(huì)丟失數(shù)據(jù)，因此通常會(huì)通過(guò)WAL（Write-ahead logging，預(yù)寫(xiě)式日志）的方式來(lái)保證數(shù)據(jù)的可靠性。

當(dāng) MemTable達(dá)到一定大小后，會(huì)轉(zhuǎn)化成Immutable MemTable。Immutable MemTable是將轉(zhuǎn)MemTable變?yōu)镾STable的一種中間狀態(tài)。寫(xiě)操作由新的MemTable處理，在轉(zhuǎn)存過(guò)程中不阻塞數(shù)據(jù)更新操作。SSTable是有序鍵值對(duì)集合，是LSM樹(shù)組在磁盤(pán)中的數(shù)據(jù)結(jié)構(gòu)。為了加快SSTable的讀取，可以通過(guò)建立key的索引以及布隆過(guò)濾器來(lái)加快key的查找。

這里需要關(guān)注一個(gè)重點(diǎn)，LSM樹(shù)（Log-Structured-Merge-Tree）正如它的名字一樣，LSM樹(shù)會(huì)將所有的數(shù)據(jù)插入、修改、刪除等操作記錄（注意是操作記錄）保存在內(nèi)存之中，當(dāng)此類操作達(dá)到一定的數(shù)據(jù)量后，再批量地順序?qū)懭氲酱疟P(pán)當(dāng)中。這與B+樹(shù)不同，B+樹(shù)數(shù)據(jù)的更新會(huì)直接在原數(shù)據(jù)所在處修改對(duì)應(yīng)的值，但是LSM數(shù)的數(shù)據(jù)更新是日志式的，當(dāng)一條數(shù)據(jù)更新是直接append一條更新記錄完成的。這樣設(shè)計(jì)的目的就是為了順序?qū)懀粩嗟貙mmutable MemTable flush到持久化存儲(chǔ)即可，而不用去修改之前的SSTable中的key，保證了順序?qū)憽?/p>

三、哈希索引

1、簡(jiǎn)介

哈希索引（hash index）基于哈希表實(shí)現(xiàn)，只有精確匹配索引所有列的查詢才有效，對(duì)于每一行數(shù)據(jù)，存儲(chǔ)引擎都會(huì)對(duì)所有的索引列計(jì)算一個(gè)哈希碼，哈希碼是一個(gè)較小的值，并且不同鍵值的行計(jì)算出來(lái)的哈希碼也不一樣。哈希碼索引將所有的哈希碼存儲(chǔ)在索引中，同時(shí)在哈希表中保存指向每個(gè)數(shù)據(jù)行的指針。
通過(guò)Hash算法（常見(jiàn)的Hash算法有直接定址法、平方取中法、折疊法、除數(shù)取余法、隨機(jī)數(shù)法），將數(shù)據(jù)庫(kù)字段數(shù)據(jù)轉(zhuǎn)換成定長(zhǎng)的Hash值，與這條數(shù)據(jù)的行指針一并存入Hash表的對(duì)應(yīng)位置；如果發(fā)生Hash碰撞（兩個(gè)不同關(guān)鍵字的Hash值相同），則在對(duì)應(yīng)Hash鍵下以鏈表形式存儲(chǔ)。因?yàn)樗饕陨碇恍璐鎯?chǔ)對(duì)應(yīng)的哈希值，所以索引的結(jié)構(gòu)十分緊湊，這也讓哈希索引查找的速度非常快。

2、局限性

哈希索引只包含哈希值和行指針，而不存儲(chǔ)字段值，所以不能使用索引中的值來(lái)避免讀取行，不過(guò)，訪問(wèn)內(nèi)存中的行的速度很快，所以大部分情況下這一點(diǎn)對(duì)性能的影響并不明顯。哈希索引數(shù)據(jù)并不是按照索引值順序存儲(chǔ)的，所以也就無(wú)法用于排序。哈希索引也不支持部分索引列匹配查找，因?yàn)楣Ｋ饕冀K是使用索引列的全部?jī)?nèi)容來(lái)計(jì)算哈希值的。哈希索引只支持等值比較查詢，包括=、IN()、<=>、也不支持任何范圍查詢。訪問(wèn)哈希索引的數(shù)據(jù)非常快，除非有很多哈希沖突（不同的索引列值卻有相同的哈希值）。當(dāng)出現(xiàn)哈希沖突的時(shí)候，存儲(chǔ)引擎必須遍歷鏈表中所有的行指針，逐行進(jìn)行比較，直到找到所有符合條件的行。如果哈希沖突很多的話，一些索引維護(hù)操作的代價(jià)也會(huì)很高。例如，如果在某個(gè)選擇性很低（哈希沖突很多）的列上建立哈希索引，那么當(dāng)從表中刪除一行時(shí)，存儲(chǔ)引擎需要遍歷對(duì)應(yīng)哈希值的鏈表中的每一行，找到并刪除對(duì)應(yīng)的引用，沖突越多，代價(jià)越大。

因?yàn)檫@些限制，哈希索引只適用于某些特定的場(chǎng)合。而一旦適合哈希索引，則它帶來(lái)的性能提升將非常顯著。舉個(gè)例子，在數(shù)據(jù)倉(cāng)庫(kù)應(yīng)用中有一種經(jīng)典的“星型” schema，需要關(guān)聯(lián)很多查找表，哈希索引就非常適合查找表的需求

延伸閱讀1：靜態(tài)哈希簡(jiǎn)介

基于散列技術(shù)的文件組織使我們能夠避免訪問(wèn)索引結(jié)構(gòu)，同時(shí)也提供了一種構(gòu)造索引的方法。在對(duì)散列的描述中，使用桶（bucket）來(lái)表示能存儲(chǔ)一條或多條記錄的一個(gè)存儲(chǔ)單位。通常一個(gè)桶就是一個(gè)磁盤(pán)塊，但也可能大于或者小于一個(gè)磁盤(pán)塊。