隨著使用數據庫的深度和理解能力的提升，有一個問題硬件的提升,與數據量的變化是否對數據庫底層的架構有沖擊。?我們公認的BTREE B+TREE ?是否還能面對現在的硬件的變化。?

BTREE?到底是為那種硬件邏輯來服務的，這點是需要搞清楚的

在MYSQL 中使用的B+TREE的改進版中底層的數據也是有指針的，便于數據順序的讀取和查找。但在怎樣寫入一次數據，需要分兩次寫入，這是B+TREE本身結構所需要的。

在數據的讀取中，磁頭讀取數據的速度是非常快的，納秒基本上服務器級別的磁盤是可以達到的，但慢在磁頭的移動，最近忘記哪家公司了，希捷還是西數發明了雙向磁頭，宣稱數據讀取的速度提高了200%. 所以B+TREE 要解決的主要問題就是我們的傳統磁盤的性能問題，通過優化數據結構來提高一次數據的盡量不要偏移磁頭，一次磁頭能讀取的數據越多，越準確越好。

所以無論是ORACLE ,SQL SERVER ,PG , MONGODB , MYSQL 的數據塊的索引均都支持 B+TREE的類型，并且有點數據庫就僅僅有這一種數據結構。

時代不同了，SSD 已經很多年了，雖然價格和傳統磁盤相比還是太高，但你敢說你最近兩年內買的筆記本上沒有他的身影。硬件的變化并不是和部分人想的，僅僅是系統性能的提高，數據的讀取的效率提高。?

硬件推動的很可能是某個工作的消失，甚至是某種數據結構的淘汰。例如原先某個SQL 優化的工作，由于更換了更快的CPU ,更大的內存， SSD 磁盤系統，原先很爛的SQL 不在是問題，你優化的“事業”，就此葬送在硬件的更新換代上。

所以害死?的，并不一定是賣豬肉的，很可能是因為牛肉更便宜了。BTREE 是為傳統磁盤來服務的，那SSD 磁盤對于 BTREE的方式可能并不感冒，如果你使用的SSD 磁盤， POSTGRESQL 中的某些配置文件中的某些參數都有可能要大動干戈。

?Unfortunately, standard disk-based index structures such as the B-tree will effectively double the I/O cost of the transaction to maintain an index such as this in real time, increasing the total system cost up to fifty percent.? Clearly a method for maintaining a real-time index at low cost is desirable.? The Log-Structured Merge-tree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period.?

LSM tree 的目的，上面的截圖的文字中，BTREE 會連浪費I/O COST ，所以LSM tree 這樣的數據結構為了就是，高并發的寫入而準備的。

下面就引入一個Knowledge?Sharing， Why? LSM Tree? Fast

首先我們需要確認LSM 要解決一個什么問題，更快速的寫，更快速的讀，并且是大量的數據的情況下。

LSM 的主體思想可以這樣來表達，數據首先寫入到buffer 然后當達到一個閾值的情況下，將數據順序整理后刷新到磁盤中。(由于在內存中預先整理，所以順序寫的速度，在傳統磁盤中也是很快的)

那這樣的情況下，就會產生另外一個問題，讀數據的困難，寫是有序寫入并且有內存進行批量的數據刷新，這放到哪個地方都是提升寫性能的一種方式，但數據要被讀取的時候，就會產生一個問題，我怎么去找到我的數據。如果順序的去查找，那將.......

那么怎么提升讀的性能就是LSM?TREE 要考慮的事情，我們可以利用bloom 過濾器，bloom 過濾器常常用在大數據量中的數據排除的活動，這是Bloom 過濾器的特性(之前寫過一篇關于bloom 過濾器，應該是和postgresql有關的一篇文字)，這里簡單的一句話bloom說你要查找的值沒有，他一定沒有，但如果他說有，有可能是錯誤，但問題是他的速度是非常快的，所以通過bloom過濾器，加上一個內存buffer 指針(保存實際的數據的物理地址，這里可以理解為index)來進行數據的讀取，原則上是可以增加數據的讀取的速度和準確度

并且在這個期間，是要對磁盤中的文件進行merge的，如何merge 以及 merge的 頻率就會直接影響整套系統的，是更偏向于寫入的性能還是讀取的性能

這里稍微的小結一下，Btree 我們知道，由于數據的插入需要符合B+TREE的原理的，所以一定會有數據的空點(頁面會split or merge)，但LSM TREE 對數據空間的利用率要比B+TREE 干脆的多。

具體LSM tree 在磁盤上的文件的實現SSTable，相信稍微懂一點cassandra的同學對這個名詞是不會陌生的，SSTABLE可以理解為是磁盤駐留的有序不可變數據結構。從結構上看，SSTable分為兩部分:數據塊和索引塊(請看下圖)，數據塊由按鍵順序寫入的唯一鍵/值對組成。索引塊包含映射到數據塊指針的鍵，這些鍵指向實際記錄所在的位置。索引可能是B-tree，或者散列表來實現查詢。SSTable中的每個值項都有一個與之關聯的時間戳，標記了插入時間。SSTables是從鍵到值是持久的、有序的、不可變的映射，其中鍵和值都是任意的字節字符串

由于SSTable是不可變的，插入、更新或刪除操作將需要重寫整個文件，主要它是針對讀、順序寫進行優化的，沒有預留空間允許任何就地修改，用大白話講就是這個SSTABLE 的磁盤數據存儲的結構，會跟隨著數據的變動不停的進行刷新合并操作。所有的Insert 操作還是Insert 操作，所有的UPDATE 操作也可以理解為insert NEW 的操作,delete 的操作也是記錄一個標記，在下次文件合并的過程中，會將其去，也可以稱這個過程叫壓縮。(也就是一KEY VALUE數據會有多個版本)

此時會重提上面提到的兩個問題，1 為什么要有時間戳的概念，時間戳的概念主要是在合并時，如有相同的數據，以時間戳最后的為準 2 合并會增加數據的順序性，讓后面的數據查找更快速。

寫到這里不能不終止了，因為沒有人愿意去看一篇長篇大論，并且毫無樂趣，因為一篇文字是需要點沖突點，來引起人們閱讀的興趣。

那下面的沖突點， LSM TREE 和? BTREE?之間的不同點在哪里

1 BTREE 是固定，一個頁面可以從2KB - 32KB大小，具體要和磁盤的結構吻合。

2 LSM TREE 則設計是沒有這樣固化的概念

1 B+TREE 可以在PAGE 頁內部進行修改更新，刪除。

2 LSM-TREE 的操作可以理解為 insert ?new , append one

1?B+TREE?對數據讀取的支持是高效的，尤其對于順序讀的操作，維護B+TREE的操作會不斷的分裂和合并，隨機的讀寫的操作的性能隨著數據的增加，會降低

2 ?LSM-TREE 本身寫入的特點，支持高容量的高并發的寫操作，這是一個分布式系統可能更加看重的，本身讀取數據的效率是隨著相關索引的優化來進行改變的，理論上讀的碎片也可以接近于 B+TREE。

這里就引出了另一個話題，LSM-TREE的合并操作會占用大量的CPU 和I/O ，這難道不會影響系統性能，OK， 所以及回到這篇文字的開頭，一個硬件的是可能改變一個數據庫的底層架構，讓其在某些情況下讓某些不可能，變為可能。

總結

以上是生活随笔為你收集整理的odoo tree视图过滤数据_数据存储结构 LSM Tree PK B TREE (从底层了解数据库设计)...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。