DDIA閱讀紀錄(8) – 第三章續：從底層檔案結構到索引結構

(進度：loc 1668 – 2353)

爆忙了一陣，竟然已經整整一週沒繼續寫這個系列了。恐怖，在家上學太恐怖了 …

這個部分首先從兩種database engine底層常見的檔案結構開始提起：LSM-tree與B-tree。這讓我回想起了大學時代修檔案結構(file structure)的血淚史，期末作業就是實作一個最基本的B-tree，後來太多人卡住，大家還聯合起來去向教授求情，才得以寬限一週。總結來說，LSM-tree(log-structured merging tree)因為針對硬碟的sequential性質去特化的存儲策略，對側重寫入的應用會有較佳的表現；但B-tree則是四平八穩，因為就是棵平衡樹，在讀取上通常表現不錯，寫入上因為隨機存取多的關係會比前者弱一些，且容易有空間破碎的問題。雖然概念上是這樣，到底何者對自身的應用才是最適合的，還是要靠實驗分析才有辦法知道。

其實就像學資料結構(data structure)一樣，許多資料結構雖然不明講，但大致上是基於von Neumann架構來設計的東西，所以實作與應用上其實都有考量到硬體性質。B-tree和LSM-tree也不例外，整個實作策略上精密地考慮了傳統硬碟的特性：存取時間長、循序讀寫佳、隨機讀寫不行，以及一定要考慮到當機復原，因為寫到硬碟裡的東西不像記憶體裡的大不了重開機治百病。

段落的最後以索引結構作結，簡單說就是這個key-value pair裡，value到底要存在哪。它可以是直接inline或說in-place跟key存在一起成為所謂的clustered index，也可以是一個heap file，也有可能是介於兩者之間，一部分在heap一部分跟index在一起成為所謂的covering index。這裡也順便提到以R-tree為代表實作的spatial index，可用於做multi-dimensional的range queries，這部份我就沒什麼實務經驗了。

下一個段落要進入Full-test search和fuzzy indexes了，這個部分和analytics data storage是我最想了解的部分，好興奮啊！希望明天不要又忙到沒時間看了啊啊啊啊啊。