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

1、LSM樹有快速的寫入性能

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

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

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

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

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

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

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

二、LSM樹介紹

1、簡介

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

LSM樹的核心特點(diǎn)是利用順序?qū)憗硖岣邔懶阅埽驗榉謱樱ù颂幏謱邮侵傅姆譃閮?nèi)存和文件兩部分）的設(shè)計會稍微降低讀性能，但是通過犧牲小部分讀性能換來高性能寫，使得LSM樹成為非常流行的存儲結(jié)構(gòu)。

2、誕生背景

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

3、核心思想

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

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

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

三、哈希索引

1、簡介

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

2、局限性

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

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

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

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