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是我最想了解的部分,好興奮啊!希望明天不要又忙到沒時間看了啊啊啊啊啊。

發表留言

Please log in using one of these methods to post your comment:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.