一、作為一個K-V數據庫，levelDB索引要使用LSM樹實現，而不采用哈希索引的原因

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

LSM樹的寫入性能優于哈希索引。哈希索引在插入數據時需要從鏈表中查找是否已經存在相同的哈希值的鍵，而LSM樹的寫入則是以順序的方式追加數據到磁盤中，并非順序寫入磁盤，而是寫入到內存緩存中。這種分層追加和緩存設計方式，使得LevelDB具有比哈希表更快的寫入速度。

2、LSM樹有優異的單機讀取性能

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

3、LSM樹適合處理大量數據

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

4、LSM樹支持數據范圍查詢

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

二、LSM樹介紹

1、簡介

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

LSM樹的核心特點是利用順序寫來提高寫性能，但因為分層（此處分層是指的分為內存和文件兩部分）的設計會稍微降低讀性能，但是通過犧牲小部分讀性能換來高性能寫，使得LSM樹成為非常流行的存儲結構。

2、誕生背景

傳統關系型數據庫使用btree或一些變體作為存儲結構，能高效進行查找。但保存在磁盤中時它也有一個明顯的缺陷，那就是邏輯上相離很近但物理卻可能相隔很遠，這就可能造成大量的磁盤隨機讀寫。隨機讀寫比順序讀寫慢很多，為了提升IO性能，我們需要一種能將隨機操作變為順序操作的機制，于是便有了LSM樹。LSM樹能讓我們進行順序寫磁盤，從而大幅提升寫操作，作為代價的是犧牲了一些讀性能。

3、核心思想

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

當 MemTable達到一定大小后，會轉化成Immutable MemTable。Immutable MemTable是將轉MemTable變為SSTable的一種中間狀態。寫操作由新的MemTable處理，在轉存過程中不阻塞數據更新操作。SSTable是有序鍵值對集合，是LSM樹組在磁盤中的數據結構。為了加快SSTable的讀取，可以通過建立key的索引以及布隆過濾器來加快key的查找。

這里需要關注一個重點，LSM樹（Log-Structured-Merge-Tree）正如它的名字一樣，LSM樹會將所有的數據插入、修改、刪除等操作記錄（注意是操作記錄）保存在內存之中，當此類操作達到一定的數據量后，再批量地順序寫入到磁盤當中。這與B+樹不同，B+樹數據的更新會直接在原數據所在處修改對應的值，但是LSM數的數據更新是日志式的，當一條數據更新是直接append一條更新記錄完成的。這樣設計的目的就是為了順序寫，不斷地將Immutable MemTable flush到持久化存儲即可，而不用去修改之前的SSTable中的key，保證了順序寫。

三、哈希索引

1、簡介

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

2、局限性

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

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

延伸閱讀1：靜態哈希簡介

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