lsm-tree
http://blog.sina.com.cn/s/blog_693f08470101njc7.html
http://blog.xiuwz.com/2012/04/09/large-web-algorithms-2/
總結：lsm-tree就是在內存中用多個樹緩存數據的更新，當內存滿時，在將多個樹進行合并，寫入磁盤。
如果是一個運行時間很長的b樹，那么幾乎所有的請求，都是隨機io。因為磁盤塊本身已經不再連續，很難保證可以順序讀取。磁盤本身是一個順序讀寫快，隨機讀寫慢的系統，
當寫讀比例很大的時候（寫比讀多），LSM樹相比于B樹有更好的性能。因為隨著insert操作，為了維護B樹結構，節點分裂。讀磁盤的隨機讀寫概率會變大，性能會逐漸減弱。而LSM，具有批量特性，存儲延遲，C0為內存組件，Cn為磁盤組件（Cn可以有多個，并且是從小到大，逐個合并），當C0 size達到閥值時，才會把insert批量刷新到磁盤。多次單頁隨機寫，變成一次多頁隨機寫。復用了磁盤尋道時間，極大提升效率。(C0和Cn都是有序樹，查詢效率為logN)
平衡樹，可以看到基本上一個元素下只有兩個子葉節點
抽象的來看，樹想要達成有效查找，勢必需要維持如下一種結構：
樹的子葉節點中，左子樹一定小于等于當前節點，而當前節點的右子樹則一定大于當前節點。只有這樣，才能夠維持全局有序，才能夠進行查詢。
這也就決定了只有取得某一個子葉節點后，才能夠根據這個節點知道他的子樹的具體的值情況。這點非常之重要，因為二叉平衡樹，只有兩個子葉節點，所以如果想找到某個數據，他必須重復更多次“拿到一個節點的兩個子節點，判斷大小，再從其中一個子節點取出他的兩個子節點，判斷大小。”這一過程。
這個過程重復的次數，就是樹的高度。那么既然每個子樹只有兩個節點，那么N個數據的樹的高度也就很容易可以算出了。
平衡二叉樹這種結構的好處是，沒有空間浪費，不會存在空余的空間，但壞處是需要取出多個節點，且無法預測下一個節點的位置。這種取出的操作，在內存內進行的時候，速度很快，但如果到磁盤，那么就意味著大量隨機尋道。基本磁盤就被查死了。
而b樹，因為其構建過程中引入了有序數組，從而有效的降低了樹的高度，一次取出一個連續的數組，這個操作在磁盤上比取出與數組相同數量的離散數據，要便宜的多。因此磁盤上基本都是b樹結構。
不過，b樹結構也不是完美的，與二叉樹相比，他會耗費更多的空間。在最惡劣的情況下，要有幾乎是元數據兩倍的格子才能裝得下整個數據集（當樹的所有節點都進行了分裂后）。
（索引通常是非常大的，不能全部放入內存，對于二叉樹而言，最極端的情況是，節點分布的很散，所以每次讀取節點都要進行一次隨機的磁盤讀取。而對于B樹而言，每個節點都存放一個有序數組，這個數組往往比較大，這樣的話，樹的高度就大大降低，通常可以看做高度為2，這樣在查詢的時候只需要磁盤讀取2次，一次讀取一個數組）
B樹的缺點是：
1. 會占用更多的空間
2.?
但如果有更新插入刪除等綜合寫入，最后因為需要循環利用磁盤塊，所以會出現較多的隨機io.大量時間消耗在磁盤尋道時間上。
如果是一個運行時間很長的b樹，那么幾乎所有的請求，都是隨機io。因為磁盤塊本身已經不再連續，很難保證可以順序讀取。
首先來分析一下為什么b+樹會慢。
從原理來說，b+樹在查詢過程中應該是不會慢的，但如果數據插入比較無序的時候，比如先插入5 然后10000然后3然后800 這樣跨度很大的數據的時候，就需要先“找到這個數據應該被插入的位置”，然后插入數據。這個查找到位置的過程，如果非常離散，那么就意味著每次查找的時候，他的子葉節點都不在內存中，這時候就必須使用磁盤尋道時間來進行查找了。更新基本與插入是相同的
那么，LSM Tree采取了什么樣的方式來優化這個問題呢？
簡單來說，就是放棄磁盤讀性能來換取寫的順序性。
乍一看，似乎會認為讀應該是大部分系統最應該保證的特性，所以用讀換寫似乎不是個好買賣。但別急，聽我分析之。
1.??????內存的速度遠超磁盤，1000倍以上。而讀取的性能提升，主要還是依靠內存命中率而非磁盤讀的次數
2.??????寫入不占用磁盤的io，讀取就能獲取更長時間的磁盤io使用權，從而也可以提升讀取效率。
因此，雖然SSTable降低了了讀的性能，但如果數據的讀取命中率有保障的前提下，因為讀取能夠獲得更多的磁盤io機會，因此讀取性能基本沒有降低，甚至還會有提升。
而寫入的性能則會獲得較大幅度的提升，基本上是5~10倍左右。
下面來看一下細節
其實從本質來說，k-v存儲要解決的問題就是這么一個：盡可能快得寫入，以及盡可能快的讀取。
讓我從寫入最快的極端開始說起，闡述一下k-v存儲的核心之一—樹這個組件吧。
我們假設要寫入一個1000個節點的key是隨機數的數據。
對磁盤來說，最快的寫入方式一定是順序的將每一次寫入都直接寫入到磁盤中即可。
但這樣帶來的問題是，我沒辦法查詢，因為每次查詢一個值都需要遍歷整個數據才能找到，這個讀性能就太悲劇了。。
那么如果我想獲取磁盤讀性能最高，應該怎么做呢？把數據全部排序就行了，b樹就是這樣的結構。
那么，b樹的寫太爛了，我需要提升寫，可以放棄部分磁盤讀性能，怎么辦呢？
簡單，那就弄很多個小的有序結構，比如每m個數據，在內存里排序一次，下面100個數據，再排序一次……這樣依次做下去，我就可以獲得N/m個有序的小的有序結構。
在查詢的時候，因為不知道這個數據到底是在哪里，所以就從最新的一個小的有序結構里做二分查找，找得到就返回，找不到就繼續找下一個小有序結構，一直到找到為止。
很容易可以看出，這樣的模式，讀取的時間復雜度是(N/m)*log2N 。讀取效率是會下降的。
這就是最本來意義上的LSM tree的思路。
那么這樣做，性能還是比較慢的，于是需要再做些事情來提升，怎么做才好呢？
于是引入了以下的幾個東西來改進它
1.??????Bloom filter : 就是個帶隨即概率的bitmap,可以快速的告訴你，某一個小的有序結構里有沒有指定的那個數據的。于是我就可以不用二分查找，而只需簡單的計算幾次就能知道數據是否在某個小集合里啦。效率得到了提升，但付出的是空間代價。
2.??????小樹合并為大樹： 也就是大家經常看到的compact的過程，因為小樹他性能有問題，所以要有個進程不斷地將小樹合并到大樹上，這樣大部分的老數據查詢也可以直接使用log2N的方式找到，不需要再進行(N/m)*log2n的查詢了。
這就是LSMTree的核心思路和優化方式。
今天來聊聊lsm tree，它的全稱是log structured merge tree ，簡單來說，lsm tree可以認為是針對傳統b樹在磁盤寫入上低劣表現的一種優化，其核心思想的核心就是放棄部分讀能力，換取寫入的最大化能力。所以你可以看到幾乎所有的nosql都在跟b樹拼寫入速度和延遲。這是為什么呢？ 看了今天的文章大家就應該能夠有個比較清晰的認識了：）
要了解lsm面臨并解決的問題，那么就需要先隨我一起回顧兩個問題:
1、磁盤的技術特性。對磁盤來說，能夠最大化的發揮磁盤技術特性的使用方式是:一次性的讀取或寫入固定大小的一塊數據，并盡可能的減少隨機尋道這個操作的次數。
2、b樹的寫入過程。對b樹的寫入過程是一次原位寫入的過程，主要分為兩個部分，首先是查找到對應的塊的位置，然后將新數據寫入到剛才查找到的數據塊中，然后再查找到塊所對應的磁盤物理位置，將數據寫入回去。當然，在內存比較充足的時候，因為b樹的一部分可以被緩存在內存中，所以查找塊的過程有一定概率可以在內存內完成，不過為了表述清晰，我們就假定內存很小，只夠存一個b樹塊大小的數據吧。可以看到，在上面的模式中，需要兩次隨機尋道（一次查找，一次原位寫），才能夠完成一次數據的寫入，代價還是很高的。
這就是下面了解LSM所需的必要前置知識了，可以很容易的看出，傳統b樹在寫入的時候需要兩次的隨機尋道，這兩次尋道會導致寫入性能存在比較大的瓶頸，導致傳統B樹的寫入效率比較低。
那么，有沒有辦法能夠對這個bad case進行調優呢？自然而然的就會想到，如果能夠減少或不進行隨機尋道，不就能夠自然而然的提升寫入效率了么？ 這就需要我們來進行一下分析，看看這些尋道主要做了什么事兒，以及如果省略了會有什么不良的影響。
第一次隨機尋道的主要作用是找到那個塊的數據需要被替換。 如果我們省去第一次隨機尋道這個操作，那么會有以下的兩個影響: ????1，無法完成sql中insert類的語意，該語義要求如果待插入的數據存在就拋異常說主鍵沖突，如果不存在就插入。 這個操作要求先找到當前數據的最新值并進行存在性判斷后才能完成插入。而如果不進行第一次查找，則這個操作是無法進行的。 ????2，無法保證數據塊內的有序性，原因是一個數據塊其實是包含了一組個數有限的有序數據的(包括待寫入的數據本身)，如果沒有取出待寫入的目標塊，那么自然就不知道要待寫數據的前后都是哪些數據了。 舉個例子： 開始的時候有9個數據，0，1，2|3，4，5|6，7，9。 每三個組織成一個塊，也就是0，1，2組成一個塊;3，4，5組成一個塊；6，7，9組成一個塊。 那么，對一個b樹而言，如果他要寫入一個數據8，他需要先取出第三個block(6，7，9)，然后判斷這個block是否有足夠的空間寫入，發現最大只有仨位置，于是就需要進行分裂。變成倆block，然后將新的數據寫入。最后寫出來的樣子可能類似0，1，2|3，4，5|6，7，空|8，9，空 然而，如果沒有查找這個步驟，那么我們自然的就不知道8這個數的周圍是哪幾個數了，也就不可能進行分裂等操作了。 ? 第二次隨機尋道的作用是在內存滿了的情況下，將數據刷寫回到磁盤的原有位置。 當內存寫滿之后，我們面臨的最主要問題就是如何解決刷磁盤的時候有哪些策略。
第一種策略可以叫做原位寫入，也就是把數據盡可能的寫回到原來的位置。 這種方式的最大好處是不會有空間的過多浪費，原來占用多大的空間，那么只要不分裂，還是占用那么多空間，沒有過多的空間浪費。同時，查詢也能保證是O(log2n)不會過多劣化，這個我們在隊尾寫的時候再進行比較。 這也是目前innodb等常見數據庫在使用的B-Tree結構。
第二種模式叫做隊尾寫入，也就是不做原位替代，只將新寫入的數據追加到整個數據的尾部。使用這種方式的好處是可以減少一次寫入時的隨機尋道時間，加快寫入的速度，不過，這樣做會有個最大的問題在于，數據的老值還存在于數據塊中，這些數據也會占用額外的空間。。 例如，開始的時候有9個數據，0，1，2|3，4，5|6，7，9。 每三個組織成一個塊，也就是0，1，2組成一個塊;3，4，5組成一個塊；6，7，9組成一個塊。那么這時候要寫一個數據8 ，再寫個數據9'，再寫個數據比如5'，在隊尾寫的時候，他就是很簡單的直接將數據按照3個一組的方式放在隊尾，那么最后數據可能類似這樣： 樹1:0，1，2|3，4，5|6，7，9; 樹2:5'，8，9' 。
這樣我們就必須處理兩個問題，一個是如何讀取到數據的最新值，另外一個問題在于如何解決空間額外浪費比較嚴重的問題。 對于數據最新值的問題，
第一種能想到的做法是每次都將內存中的樹和硬盤中的樹做合并后寫到新的位置，并更新父節點的指針。 這種方的好處是查詢可以得到很好的性能，劣勢在于磁盤增刪次數多了以后，會存在磁盤空洞比較嚴重的問題，需要在compaction的時候做好磁盤整理，同時對范圍查詢不友好，因為數據在多次增刪之后是隨機跳躍存在的，所以讀取時候的隨機io會變的更多。
第二種能想到的做法是分開大的有序樹和小的有序樹，對于上面的例子而言，我們可以認為，“0，1，2|3，4，5|6，7，9” 是一棵大的有序樹，而5'，8,，9' ?是一顆小的有序樹。內存內也可以有一個或多個有序樹的結構。這樣，在每顆樹的時間復雜度都是O(log2n) ，而如果寫入比較重，那么存在了N個小的有序樹沒有合并，那么讀取一個數據的時候，可以根據時間順序倒著去多個樹中依次查找，那么只要能找到數據，就一定是該數據的最新值了。
而對于空間額外浪費比較嚴重的問題，一般的解決方式就是再開一個線程， 利用合并排序的方式將多個小的有序數樹進行合并后的追加寫。 因為這個操作也是后臺異步并行進行的，并且寫出來的數據也是順序有序的，所以也可以盡可能的降低磁盤的隨機尋道次數。 如使用上面的例子，那么這次歸并就是把 “0，1，2|3，4，5|6，7，9” ?這個有序樹與"5'，8,，9' " 這個有序樹做歸并排序，最后得到的磁盤結構類似 “樹1：0，1，2|3，4，5|6，7，9;樹2:5'，8，9' ;樹3:0，1，2|3，4，5'|6，7，8|9'" ?，然后因為樹3已經合并完成并包含了樹1和樹2 的最新值，于是樹1和樹2就可以被標記為刪除了，最后磁盤中留下的就是”樹3:0，1，2|3，4，5'|6，7，8|9'" ，一般我們會有一個專門的英語單詞來代表這個過程：compation。使用隊尾追加的數據結構的人就太多了， cassandra , levelDB , hbase 等等都是使用這種結構來寫入數據的，因此你會發現使用這樣的數據結構的存儲引擎，在寫入效率上都明顯的好于原位寫，而讀取則因為需要查找更多棵在磁盤的樹而會使用更多的磁盤io.
然后把這兩兩次隨機尋道做一次結合。就能發現幾個合理的解決思路: 解1. 如果需要sql中的insert操作，那么就必須進行第一次隨機尋道。 解2. 如果使用隊尾寫入的時候，是不需要進行第二次隨機尋道的。結合解1，就可以完全的避免在寫入時的隨機尋道了，代價是讀效率的降低或者更多的碎片問題。 解3. 針對原位寫，可以進行將原來單獨寫回的操作變成批量寫回操作。這樣就可以提升順序寫的概率，從而提升寫入效率。
這基本上就是目前我們能夠為磁盤做的一切了：）
了解了核心思路之后，下面我們來看看我們經常看到的三個詞匯的具體含義，就比較容易的可以理解了:
第一個是LSM Tree ，這個概念就是結構化合并樹的意思，它的核心思路其實非常簡單，就是假定內存足夠大，因此不需要每次有數據更新就必須將數據寫入到磁盤中，而可以先將最新的數據駐留在磁盤中，等到積累到最后多之后，再使用歸并排序的方式將內存內的數據合并追加到磁盤隊尾(因為所有待排序的樹都是有序的，可以通過合并排序的方式快速合并到一起)。這就是LSM Tree的核心定義。?
對應到上面的就是解2的所有可能性實現。
第二個概念是Merge-Dump 模型的LSM Tree， 就我目前理解而言，這個概念表述的是一種特殊的LSM tree實現，對應在LSM Tree論文里應該是 Multi-Component LSM Tree 。LSM Tree有個最大的問題就是如果合并速度比較慢，寫入速度比較快，那么可能一次合并周期內用戶所寫入的數據會遠遠大于內存的大小，這樣就不得不需要一個非常大的內存空間才能滿足lsm tree的寫入要求，這明顯是不可能的。為了解決這一矛盾，能夠想到的方案就是定期將內存數據直接刷寫到磁盤尾部并將內存清空，這樣就可以保證數據以磁盤最大吞吐量寫入而不會出現內存溢出的情況。 并且可以讓合并操作異步化，從而讓寫入更平滑。代價則是在查詢時會消耗更多的隨機io查詢。 對應到上面就是解2的一個特例。
第三個概念就是SSTable. 就我目前理解而言，這個概念表述的是一種特殊的Merge-Dump模型的LSM Tree , 關鍵特征是key是按照字典序排好的”字符串“的merge-dump樹:)。 也對應上面的解2特例的一個特例。
第四個概念是傳統b樹， 一般來說傳統b樹的優化策略是解3，也就是原位更新，使用分裂合并的策略來完成數據數據在磁盤上的擴展。 對應上面策略中的解3.
了解了核心概念，我們再分別針對幾個標志性的場景做一下擴展性分析。
首先回答的一個問題是為什么原位的存儲結構，例如innodb，會在寫入刪除多次之后性能下降呢？
在大家經常能夠看到的性能指標中，都會看到innodb這類原位寫的磁盤存儲結構會在使用一段時間以后出現效率下降的問題，而hbase/cassandra 等所使用的sstable則不會出現這類的下降，那么自然就會有個疑問，這是為什么呢？ 其實原因不復雜，核心的問題在于磁盤空洞，在多次寫入之后，數據在磁盤上可能是類似這樣的 ”0，1，2|空洞|8，9，11|空洞|4，5，6|"，雖然在邏輯上，B樹是個有序的樹狀結構，但是在實際磁盤上數據卻是按照塊組織的， 在進行分裂的時候，會從空池中找出一個能放下數據的塊，然后就進行寫入，這樣如果經過多次寫入擦除輪回之后，可進行連續寫入的空間就會變的很少，于是就會導致一些看起來是順序寫的過程，在磁盤上變成了隨機寫。從而導致了寫入性能的下降。需要做后臺數據整理，把空閑塊變得更連續，才有可能再次提升寫入性能。
第二個問題是針對Merge-Dump結構的存儲結構，是不是讀取都是爛的沒法要了？ 這個問題的答案是否定的，因為雖然因為是隊尾追加小樹，所以要找到數據的最新值的時候，讀取的時間復雜度從原來的O(log2n)變成了O(N*log2n) ,效率直線下降了很多，不過我們仍然有很多方式來對讀取進行一些優化，讓這件事變得沒有那么的夸張。 那么為了能夠提升讀取效率，可以考慮去做的事情有以下幾個： 第一件事就是一個設計良好的數據緩存系統，在大部分情況下，如果你的查詢能夠命中緩存，那么將在內存以O(log2n)即可命中并返回數據。在目前內存越來越大的機器上而言，這是一個最直接而簡單的提升Merge-Dump結構的讀取效率的方式。 第二件事是一個設計良好的compaction實現，這其實才是Merge-Dump數據結構寫入效率的關鍵，因為在大部分情況下，compaction過程會與寫入線程爭搶磁盤的io資源，如果兩個事情同時進行，甚至還會額外的增加隨機io次數。因此，如何能夠平衡和高效的完成磁盤compaction的過程，是一個存儲引擎實現好壞的關鍵。另外的一個關鍵的問題是在什么時候觸發compaction. 觸發的時間早了，會造成資源爭搶，而觸發的時間晚了。會造成大量磁盤空間的浪費，目前主流的實現中，基本上都會以sstable的個數或者時間點作為觸發條件。各位可以按照自己的實際需要進行配置，以達到最佳的處理效果。 第三件事就是可以考慮增加bloom-filter來提升查找效率，我在這里只說bloom-filter能做到的事情和具體舉一個例子，不展開具體實現方式，各位感興趣可以自行查詢。bloom-filter在這里的作用在于能夠以O(1)的效率判斷一個待查的數據是否在一個小樹中。 那么在一大堆小樹中，我們要查找某個數據是否在某個小樹中，只需要以O(N)的效率遍歷這些小樹就可以快速的找到這個數據具體在哪個樹中，比使用O(N*log2n)的查找效率就快了不少，代價是額外的寫入時cpu消耗，以及額外的一些空間。
第三個問題是，是不是用了Merge-Dump模型的LSM Tree實現的存儲結構實現的數據庫，效率就一定會有很大的提升了？
是，也不是 首先，假定沒有任何其他優化，那么使用Merge-Dump模型的LSM Tree實現的數據庫的在實現"insert"這個語義的時候，也是需要一次隨機尋道來判斷“數據是否存在”的， 這額外增加了成本。所以你會發現NoSQL里面默認提供的語義是put ， 也就是無論數據是否存在，都將數據以覆蓋寫入的方式寫入到存儲中，這種方式是針對merge-dump而言消耗最小的寫入模式。 其次，數據庫中還有一塊比較重的邏輯在事務關系，也就是以MVCC的方式保證針對一條或多條數據的多次更新能夠保持一個統一而一致的用戶狀態。 這會額外的增加一些開銷，從而降低了系統的整體性能。
最后一個問題是：我應該選擇哪個？
答案還是選合適的。沒有一種數據結構能夠包打天下，Merge-Dump類的數據結構（如sstable)，優勢在寫入速度快，劣勢在讀取消耗資源大。而原位寫的數據結構，如innodb類的結構，優勢在于讀寫比較平衡，尤其對于讀取有比較大的優化。 就阿里集團的實際使用經驗來說，如果你日常的寫入與讀取操作的比率小于1:2，那么選擇寫優化的存儲結構是非常合適的。而如果超過這個閾值，那么選擇面向讀取優化的數據結構是最為合適的。
做一下簡單的小結，LSM Tree和傳統B樹最大的區別就在于數據合并的策略，是采用原位替換的模式，還是采用合并追加到隊尾的方式來進行數據合并。采用追加隊尾的方式，對于磁盤寫入來說會有極大的性能提升，代價一般是讀取效率的降低。而對于傳統B樹來說，讀取和寫入則更為平衡，適合一般性場景，不適合寫入讀取比率比較高的場景。
最后，還是老規矩，讓我們以綜合評價作為本篇的結束。 1.是否支持范圍查找
因為是有序結構，所以能夠很好的支持范圍查找。
2.集合是否能夠隨著數據的增長而自動擴展
可以，與Btree的方式一致
3.讀寫性能如何
對于寫入來說，Merge-Dump類的數據結構能夠盡可能的減少寫入時的磁盤尋道次數，所以寫入能夠到達磁盤吞吐量的上限，寫入比較平穩，而原位寫的數據結構則會存在磁盤空洞問題，導致寫入性能有一定下降。 對于讀取來說，Merge-Dump不占優勢，當然因為有cache和compaction ，所以效率不會下降很多，但是因為每次讀取需要與寫入線程爭用磁盤隨機尋道次數，所以他們之間也會相互影響，從而降低性能。 對于原位寫的數據結構來說，查詢的效率能夠做到固定的隨機尋道次數，比較理想。
4.是否面向磁盤結構
一般來說，在有內存的情況下，root層和branch里面的一部分都會被緩存在內存中，所以如果樹的高度是三層，那么前兩層一般都會被緩存在內存中，所以查詢基本上只需要一次隨機尋道時間，是一個面向磁盤的結構
5.并行指標
對于LSM類數據結構來說，并行指標主要由兩個部分組成，第一個部分是內存中樹的并行指標，第二個是在磁盤中樹的并行指標。 以目前主流的實現而言，都可以做到比較好的并行。
6.內存占用 這個主要看在內存中選擇了哪個數據結構，以及在內存中維持了幾個小樹，小樹越多，那么內存額外消耗的就多，而如果內存中小樹比較少，那么內存中的消耗就少。
The Log-Structured Merge-Tree
在說LSM-Tree之前，首先說下該算法的來由。在上一章節中，提到了非常經典的B+樹數據模型。B+樹非常適合磁盤存儲，也很適合順序寫入，但對于隨機寫則是其致命傷。業界針對B+樹隨機寫的優化，通常有兩種方式：
LSM-Tree軟件解決方案的基本原理都非常簡單，就是在內存中對最近的更新操作進行緩存，當更新積累到一定程度，然后進行批量的merge dump，從而把隨機寫變成批量順序更新。典型的架構如下圖：
在上圖中有幾個關鍵點：
1、memtable。內存結構映像，更新都是首先更新到memtable。
2、tablet log，也稱為redo log。主要用于在異常情況下，對memtable的重建。
3、讀操作需要從sstable和memtable中讀取，并進行merge返回。
LSM-Tree最早是由Patrick O’Neil 等在1996年提出來的，論文在這里。中文版本可以參考這里：上、中、下。下面是一個LSM-Tree的merge過程示意圖。
在實際應用中，都會對LSM-Tree進行一些優化，比如說leveldb中lsm-tree和skip-list的結合、bigtable在merge過程中并發控制等等。同時也基于此產生了大量相關的算法，比如說cache-oblivious B-tree、buffer tree等等。推薦看看Tokutek的這幾篇文章：Detailed review of Tokutek storage engine、Performance of Fractal-TreeDatabases。
總結
- 上一篇： android读写文件
- 下一篇： 数据映射--B树