5

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

 3 years ago
source link: https://softman.blog/2021/06/08/ddia-8-ch3-file-structure-to-index-structure/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

啊...啊啊啊... _(´ཀ`」 ∠)_ 觀看 James Tien 的所有文章


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK