爲什麼LevelDB需要兩個以上的級別？

Question

我認爲只有兩個級別（level-0和level-1）可以，LevelDB爲什麼需要level-2，level-3和更多？

Answer 1

我會指出你在LevelDB上的一些文章的方向，它的基礎存儲結構。

所以在documentation for LevelDB 它討論級別之間的合併。

這些合併具有使用僅批量讀取和寫入（即最小化昂貴的查找）逐漸將新更新從年輕級別遷移到最大級別的效果。

LevelDB在結構上與Log Structured Merge Trees類似。本文討論不同層次，如果你有興趣分析它。如果你可以通過數學來理解數據結構似乎是你最好的選擇。

一個更易於閱讀有關數據存儲的關係LSM樹性LevelDB會談analysis但在你對各級它說的問題方面是：

最後，有數百個磁盤上SSTables的是也不是一個好主意，因此我們會定期運行一個進程來合併磁盤上的SSTables。

可能LevelDB文檔提供了最佳答案:(由於LevelDB是磁盤（慢查找）數據存儲，因此最大化寫入和讀取的大小）。

祝你好運！

Answer 2

我認爲這主要是爲了輕鬆快速地合併關卡。

在Leveldb中，level-（i + 1）大約有。與第一級相比數據的10倍。這更類似於多級緩存結構，其中如果數據庫在鍵x1至x2之間具有1000條記錄，那麼該範圍中最常訪問的10條記錄將在1級中，並且100個在相同範圍中在二級和休息在三級（這不是確切的，但只是提供一個直觀的水平）。在這個設置中，爲了合併文件在level-i中，我們需要查看最多10個文件（level）（i + 1），它可以全部放入內存，快速合併完成並寫回。這些結果爲每個壓縮/合併操作讀取相對較小的數據塊。

另一方面，如果你只有2個級別，一個0級文件的關鍵範圍可能匹配1級1000個文件，並且所有這些文件都需要打開合併，這將是很慢。請注意，這裏一個重要的假設是我們有固定大小的文件（比如2MB）。對於level-1中的可變長度文件，您的想法仍然可以工作，並且我認爲HBase和Cassandra等系統中使用了該變體。

現在，如果您關心的是關於多級查找延遲的問題，這又像是一個多級緩存結構，最近寫入的數據將處於更高級別以幫助典型的參考位置。

Answer 3

0級是內存中的數據，其他級別是磁盤數據。重要的部分是對數據進行排序。如果level1由3個2Mb文件組成，則在file1中它是file2.50..200和file3 300..400（作爲示例）中的關鍵字0..50（排序）。因此，當內存級別滿時，我們需要以最有效的方式將其數據插入磁盤，這是順序寫入（儘可能少使用磁盤查找）。想象一下，在內存中我們有60-120個按鍵，很酷，我們只是把它們順序地寫入文件中，成爲level1中的file2。非常高效！ 但是現在想象level1比level0大得多（這是合理的，因爲level0是內存）。在這種情況下，level1中有很多文件。現在我們在內存中的密鑰（60-120）屬於許多文件，因爲level1中的密鑰範圍非常細微。現在要將level0與level1合併，我們需要讀取許多文件並進行大量隨機搜索，在內存中創建新文件並編寫它們。所以這是許多層次的想法開始的地方，我們會有很多層次，每個層次都比前一個（x10）大一些，但不會太大，所以當我們必須將數據從i-1遷移到第i層時，我們有一個必須閱讀最少量的文件的好機會。

現在，由於數據可能會發生變化，因此可能無需將其傳播到更昂貴的圖層（可能會更改或刪除），因此我們可以避免昂貴的合併。最後一層的數據在統計上最不可能發生變化，因此最適合與最後一層合併成本最高的數據。