Composite image of hand holding a marker
1、Hash存儲引擎
代表數據庫：redis、memcache等
通常也常見於其他存儲引擎的查找速度優化上。 Hash 索引結構的特殊性，其檢索效率非常高，索引的檢索可以一次定位，不像B-Tree 索引需要從根節點到枝節點，最後才能訪問到頁節點這樣多次的IO訪問，所以 Hash 索引的查詢效率要遠高於 B-Tree 索引。雖然 Hash 索引效率高，但是 Hash 索引本身由於其特殊性也帶來了很多限制和弊端。
這裡列舉缺點：
（1）Hash 索引僅僅能滿足"=","IN"和"<=>"查詢，不能使用範圍查詢。
（2）Hash 索引無法被用來避免數據的排序操作。
（3）Hash 索引不能利用部分索引鍵查詢。
(4）Hash 索引在任何時候都不能避免表掃描。
Hash碰撞，就是鏈式掃描：
由於不同索引鍵存在相同 Hash 值，所以即使取滿足某個 Hash 鍵值的數據的記錄條數，也無法從 Hash索引中直接完成查詢，還是要通過訪問表中的實際數據進行相應的比較，並得到相應的結果。
（5）Hash 索引遇到大量Hash值相等的情況後性能並不一定就會比B-Tree索引高。
2、B樹存儲引擎
代表數據庫：MongoDB、mysql(基本上關係型數據庫)等
還有一種算是B樹存儲引擎：COLA樹（CacheObliviousBTree）
代表數據庫：tokudb
為了如何讓B樹更有效的執行，他們提出了一個緩存忘卻CacheOblivious算法，該算法在不需要明確知道存儲器層次中數據傳輸規模的情況下，也可以高效的工作。更多請參見：http://en.wikipedia.org/wiki/Cache-oblivious_algorithm。
說個大家熟悉的名稱TokuMX : 目前非常流行的NoSQL數據庫MongoDB的底層替換成與TokuDB同樣的存儲引擎[ ToKuMx]，達到了非常好的效 果
3、LSM樹（Log-Structured Merge Tree）存儲引擎
代表數據庫：nessDB、leveldb、hbase等
核心思想的核心就是放棄部分讀能力，換取寫入的最大化能力。LSM Tree ，這個概念就是結構化合並樹的意思，它的核心思路其實非常簡單，就是假定內存足夠大，因此不需要每次有數據更新就必須將數據寫入到磁盤中，而可以先將最新的數據駐留在磁盤中，等到積累到最後多之後，再使用歸併排序的方式將內存內的數據合併追加到磁盤隊尾(因為所有待排序的樹都是有序的，可以通過合併排序的方式快速合併到一起)。
日誌結構的合併樹（LSM-tree）是一種基於硬盤的數據結構，與B-tree相比，能顯著地減少硬盤磁盤臂的開銷，並能在較長的時間提供對文件的高速插入（刪除）。然而LSM-tree在某些情況下，特別是在查詢需要快速響應時性能不佳。通常LSM-tree適用於索引插入比檢索更頻繁的應用系統。Bigtable在提供Tablet服務時，使用GFS來存儲日誌和SSTable，而GFS的設計初衷就是希望通過添加新數據的方式而不是通過重寫舊數據的方式來修改文件。而LSM-tree通過滾動合併和多頁塊的方法推遲和批量進行索引更新，充分利用內存來存儲近期或常用數據以降低查找代價，利用硬盤來存儲不常用數據以減少存儲代價。
磁盤的技術特性:對磁盤來說，能夠最大化的發揮磁盤技術特性的使用方式是:一次性的讀取或寫入固定大小的一塊數據，並儘可能的減少隨機尋道這個操作的次數。
LSM和Btree差異就要在讀性能和寫性能進行舍和求。在犧牲的同事，尋找其他方案來彌補。
1、LSM具有批量特性，存儲延遲。當寫讀比例很大的時候（寫比讀多），LSM樹相比於B樹有更好的性能。因為隨著insert操作，為了維護B樹結構，節點分裂。讀磁盤的隨機讀寫概率會變大，性能會逐漸減弱。 多次單頁隨機寫，變成一次多頁隨機寫,複用了磁盤尋道時間，極大提升效率。
2、B樹的寫入過程:對B樹的寫入過程是一次原位寫入的過程，主要分為兩個部分，首先是查找到對應的塊的位置，然後將新數據寫入到剛才查找到的數據塊中，然後再查找到塊所對應的磁盤物理位置，將數據寫入去。當然，在內存比較充足的時候，因為B樹的一部分可以被緩存在內存中，所以查找塊的過程有一定概率可以在內存內完成，不過為了表述清晰，我們就假定內存很小，只夠存一個B樹塊大小的數據吧。可以看到，在上面的模式中，需要兩次隨機尋道（一次查找，一次原位寫），才能夠完成一次數據的寫入，代價還是很高的。
3、LSM Tree放棄磁盤讀性能來換取寫的順序性，似乎會認為讀應該是大部分系統最應該保證的特性，所以用讀換寫似乎不是個好買賣。但別急，聽我分析一下。
a、內存的速度遠超磁盤，1000倍以上。而讀取的性能提升，主要還是依靠內存命中率而非磁盤讀的次數
b、寫入不佔用磁盤的io，讀取就能獲取更長時間的磁盤io使用權，從而也可以提升讀取效率。例如LevelDb的SSTable雖然降低了了讀的性能，但如果數據的讀取命中率有保障的前提下，因為讀取能夠獲得更多的磁盤io機會，因此讀取性能基本沒有降低，甚至還會有提升。而寫入的性能則會獲得較大幅度的提升，基本上是5~10倍左右。
下面說說詳細例子:
LSM Tree弄了很多個小的有序結構，比如每m個數據，在內存裡排序一次，下面100個數據，再排序一次……這樣依次做下去，我就可以獲得N/m個有序的小的有序結構。
在查詢的時候，因為不知道這個數據到底是在哪裡，所以就從最新的一個小的有序結構裡做二分查找，找得到就返回，找不到就繼續找下一個小有序結構，一直到找到為止。
很容易可以看出，這樣的模式，讀取的時間複雜度是(N/m)*log2N 。讀取效率是會下降的。
這就是最本來意義上的LSM tree的思路。那麼這樣做，性能還是比較慢的，於是需要再做些事情來提升，怎麼做才好呢？
LSM Tree優化方式：
a、Bloom filter: 就是個帶隨即概率的bitmap,可以快速的告訴你，某一個小的有序結構裡有沒有指定的那個數據的。於是就可以不用二分查找，而只需簡單的計算幾次就能知道數據是否在某個小集合裡啦。效率得到了提升，但付出的是空間代價。
b、compact:小樹合併為大樹:因為小樹他性能有問題，所以要有個進程不斷地將小樹合併到大樹上，這樣大部分的老數據查詢也可以直接使用log2N的方式找到，不需要再進行(N/m)*log2n的查詢了
