1,、Hash存儲引擎

代表數(shù)據(jù)庫：redis,、memcache等

通常也常見于其他存儲引擎的查找速度優(yōu)化上,。 Hash 索引結構的特殊性，其檢索效率非常高,，索引的檢索可以一次定位,，不像B-Tree 索引需要從根節(jié)點到枝節(jié)點，最后才能訪問到頁節(jié)點這樣多次的IO訪問,，所以 Hash 索引的查詢效率要遠高于 B-Tree 索引,。雖然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也帶來了很多限制和弊端,。

這里列舉缺點：

（1）Hash 索引僅僅能滿足"=","IN"和"<=>"查詢,，不能使用范圍查詢。
（2）Hash 索引無法被用來避免數(shù)據(jù)的排序操作,。
（3）Hash 索引不能利用部分索引鍵查詢,。
(4）Hash 索引在任何時候都不能避免表掃描。
Hash碰撞,，就是鏈式掃描：
由于不同索引鍵存在相同 Hash 值,，所以即使取滿足某個 Hash 鍵值的數(shù)據(jù)的記錄條數(shù)，也無法從 Hash索引中直接完成查詢,，還是要通過訪問表中的實際數(shù)據(jù)進行相應的比較,，并得到相應的結果。
（5）Hash 索引遇到大量Hash值相等的情況后性能并不一定就會比B-Tree索引高,。

2,、B樹存儲引擎

代表數(shù)據(jù)庫：MongoDB、mysql(基本上關系型數(shù)據(jù)庫)等

還有一種算是B樹存儲引擎：COLA樹（CacheObliviousBTree）

代表數(shù)據(jù)庫：tokudb

為了如何讓B樹更有效的執(zhí)行,，他們提出了一個緩存忘卻CacheOblivious算法,，該算法在不需要明確知道存儲器層次中數(shù)據(jù)傳輸規(guī)模的情況下，也可以高效的工作,。更多請參見：http://en./wiki/Cache-oblivious_algorithm,。

說個大家熟悉的名稱TokuMX : 目前非常流行的NoSQL數(shù)據(jù)庫MongoDB的底層替換成與TokuDB同樣的存儲引擎[ ToKuMx]，達到了非常好的效 果

3,、LSM樹（Log-Structured Merge Tree）存儲引擎

代表數(shù)據(jù)庫：nessDB,、leveldb、hbase等

核心思想的核心就是放棄部分讀能力,，換取寫入的最大化能力,。LSM Tree ，這個概念就是結構化合并樹的意思,，它的核心思路其實非常簡單,，就是假定內存足夠大，因此不需要每次有數(shù)據(jù)更新就必須將數(shù)據(jù)寫入到磁盤中,，而可以先將最新的數(shù)據(jù)駐留在磁盤中,，等到積累到最后多之后,，再使用歸并排序的方式將內存內的數(shù)據(jù)合并追加到磁盤隊尾(因為所有待排序的樹都是有序的，可以通過合并排序的方式快速合并到一起),。

日志結構的合并樹（LSM-tree）是一種基于硬盤的數(shù)據(jù)結構，與B-tree相比,，能顯著地減少硬盤磁盤臂的開銷,，并能在較長的時間提供對文件的高速插入（刪除）。然而LSM-tree在某些情況下,，特別是在查詢需要快速響應時性能不佳,。通常LSM-tree適用于索引插入比檢索更頻繁的應用系統(tǒng)。Bigtable在提供Tablet服務時,，使用GFS來存儲日志和SSTable,，而GFS的設計初衷就是希望通過添加新數(shù)據(jù)的方式而不是通過重寫舊數(shù)據(jù)的方式來修改文件。而LSM-tree通過滾動合并和多頁塊的方法推遲和批量進行索引更新,，充分利用內存來存儲近期或常用數(shù)據(jù)以降低查找代價,，利用硬盤來存儲不常用數(shù)據(jù)以減少存儲代價。

磁盤的技術特性:對磁盤來說,，能夠最大化的發(fā)揮磁盤技術特性的使用方式是:一次性的讀取或寫入固定大小的一塊數(shù)據(jù),，并盡可能的減少隨機尋道這個操作的次數(shù)。

LSM和Btree差異就要在讀性能和寫性能進行舍和求,。在犧牲的同事,，尋找其他方案來彌補。

1,、LSM具有批量特性,，存儲延遲。當寫讀比例很大的時候（寫比讀多）,，LSM樹相比于B樹有更好的性能,。因為隨著insert操作，為了維護B樹結構,，節(jié)點分裂,。讀磁盤的隨機讀寫概率會變大，性能會逐漸減弱,。 多次單頁隨機寫,，變成一次多頁隨機寫,復用了磁盤尋道時間，極大提升效率,。

2,、B樹的寫入過程:對B樹的寫入過程是一次原位寫入的過程，主要分為兩個部分,，首先是查找到對應的塊的位置,，然后將新數(shù)據(jù)寫入到剛才查找到的數(shù)據(jù)塊中,，然后再查找到塊所對應的磁盤物理位置，將數(shù)據(jù)寫入去,。當然,，在內存比較充足的時候，因為B樹的一部分可以被緩存在內存中,，所以查找塊的過程有一定概率可以在內存內完成,，不過為了表述清晰，我們就假定內存很小,，只夠存一個B樹塊大小的數(shù)據(jù)吧,。可以看到,，在上面的模式中,，需要兩次隨機尋道（一次查找，一次原位寫）,，才能夠完成一次數(shù)據(jù)的寫入,，代價還是很高的。

3,、LSM Tree放棄磁盤讀性能來換取寫的順序性,，似乎會認為讀應該是大部分系統(tǒng)最應該保證的特性，所以用讀換寫似乎不是個好買賣,。但別急,，聽我分析一下。

b,、寫入不占用磁盤的io，讀取就能獲取更長時間的磁盤io使用權,，從而也可以提升讀取效率,。例如LevelDb的SSTable雖然降低了了讀的性能，但如果數(shù)據(jù)的讀取命中率有保障的前提下,，因為讀取能夠獲得更多的磁盤io機會,，因此讀取性能基本沒有降低，甚至還會有提升,。而寫入的性能則會獲得較大幅度的提升,，基本上是5~10倍左右。

下面說說詳細例子:

LSM Tree弄了很多個小的有序結構,，比如每m個數(shù)據(jù),，在內存里排序一次,，下面100個數(shù)據(jù)，再排序一次……這樣依次做下去,，我就可以獲得N/m個有序的小的有序結構,。

在查詢的時候，因為不知道這個數(shù)據(jù)到底是在哪里,，所以就從最新的一個小的有序結構里做二分查找,，找得到就返回，找不到就繼續(xù)找下一個小有序結構,，一直到找到為止。

很容易可以看出,，這樣的模式,，讀取的時間復雜度是(N/m)*log2N 。讀取效率是會下降的,。

這就是最本來意義上的LSM tree的思路,。那么這樣做，性能還是比較慢的,，于是需要再做些事情來提升,，怎么做才好呢？

LSM Tree優(yōu)化方式：

a,、Bloom filter: 就是個帶隨即概率的bitmap,可以快速的告訴你,，某一個小的有序結構里有沒有指定的那個數(shù)據(jù)的。于是就可以不用二分查找,，而只需簡單的計算幾次就能知道數(shù)據(jù)是否在某個小集合里啦,。效率得到了提升，但付出的是空間代價,。

b,、compact:小樹合并為大樹:因為小樹他性能有問題，所以要有個進程不斷地將小樹合并到大樹上,，這樣大部分的老數(shù)據(jù)查詢也可以直接使用log2N的方式找到,，不需要再進行(N/m)*log2n的查詢了