Designing-Data-Intensive-Applications Ch3 Note
兩大類儲存引擎：日誌結構（log-structured） 的儲存引擎，以及面向頁面（page-oriented） 的儲存引擎（例如B樹）。
日誌結構
- 試想一個簡單的資料庫程式
SET資料會不斷APPEND到一個FILE
GET資料會從頭 掃描整個檔案
—
要怎樣加速GET 資料呢？
ANSWER： 建立index
一個方法是使用 hash
value 記錯data file 的offset set
在寫入的部分，會遇到另一個問題： 空間不足
我們可以想像，因為是不斷APPEND 資料。所以重覆的KEY，其實只要保留最新的資料就可以了，EX
data file
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}---
只保留
42,{"name":"San Francisco","attractions":["Exploratorium"]}
所以解決空間的問題（起碼減少相同KEY的內容）
- 是壓縮（去除相同的KEY ）
將日誌data 分為特定大小的段，當日志增長到特定尺寸時關閉當前段檔案，並開始寫入一個新的段檔案。
單檔壓縮：
也可以多檔一起進行壓縮（在寫入FILE時，當FILE到某一大小時，就開以寫入另一個FILE。到某一程度後，進行壓縮）
現在在使用HASH 來找資料，會遇到另外的問題：
- HASH必須能放進記憶體
- 範圍查詢效率不高。例如，您無法輕鬆掃描kitty00000和kitty99999之間的所有KEY
為解決以上問題 可以使用SSTables（Sorted String Table）
SSTables和LSM樹
思路：
- 在資料壓縮後，先把KEY都Sort 存為一個新的file(或叫segment)
記得 新的FILE 的VALUE 會覆蓋舊的FILE。
這樣 回到剛剛的問題
"範圍查詢效率不高。例如，您無法輕鬆掃描kitty00000和kitty99999之間的所有KEY”
因為sort 過，我們可以知道 kitty00000 和 kitty99999 在hash 有什麼KEY了
2.FOR 問題 "HASH必須能放進記憶體” ，我們現在也不用把整個HASH 儲在MEMORY內，只要存一部分的的KEY就可以了，EX kitty00000，kitty00100， kitty00200. 不用把 kitty00000， kitty00001，kitty00002 也儲在memory 內
因為儲在 SEGMENT內 是有SORT過 ，所以我們只要存 kitty00000，和kitty00100， 知道 SEGMENT內的 OFFSET，就可以從kitty00000 OFFSET 和 kitty00100 開始找對應的資料（ex: kitty00001) ，這樣可以減少存HASH的大小
當然還有其他問題，如：
— —
另一種 資料庫 面向頁面（page-oriented） 的儲存引擎
B樹
B樹
剛才討論的日誌結構索引正處在逐漸被接受的階段，但它們並不是最常見的索引型別。使用最廣泛的索引結構在1970年被引入【17】，不到10年後變得“無處不在”【18】，B樹經受了時間的考驗。在幾乎所有的關係資料庫中，它們仍然是標準的索引實現，許多非關係資料庫也使用它們。
像SSTables一樣，B樹保持按鍵排序的鍵值對，這允許高效的鍵值查詢和範圍查詢。但這就是相似之處的結尾：B樹有著非常不同的設計理念。
我們前面看到的日誌結構索引將資料庫分解為可變大小的段，通常是幾兆位元組或更大的大小，並且總是按順序編寫段。相比之下，B樹將資料庫分解成固定大小的塊或頁面，傳統上大小為4KB（有時會更大），並且一次只能讀取或寫入一個頁面。這種設計更接近於底層硬體，因為磁碟也被安排在固定大小的塊中。
每個頁面都可以使用地址或位置來標識，這允許一個頁面引用另一個頁面 — — 類似於指標，但在磁碟而不是在記憶體中。我們可以使用這些頁面引用來構建一個頁面樹
頁：
—
加入新的KEY，如果頁內容已經滿了，會分裂成兩個頁，並更內父頁ref