London Tech Talk 名物 Bookclub 第四弾 "Database Internals" 第六章の振り返り収録です。"B-Tree Varients" の内容について振り返りました。

まず B Tree (B+ Tree) の簡単なおさらいをしました。B Tree のかかえる Write Amplification や Space Amplification という課題を解決するために B Tree の亜種が開発される必要があったという前提についてまずは理解しましょう。

最初に紹介したのは Lazy B-Trees です。Buffering というテクニックを利用して書き込みによる木構造の Node Split や Node Merge の頻度を下げる工夫について紹介しました。具体的には MongoDB のストレージエンジンでもある WiredTiger や Lazy-Adaptive Tree について触れました。

続いて Flash-Disk Tree (FD-Tree) について紹介しました。Buffering の議論を推し進めて、Chapter 7. でも紹介する LSM Trees をインスパイアーしたとされる FD Tree のキーワードについて紹介しました。

最後に、Microsoft から 2013 年に発表された Buzzword-Tree について紹介しました。マルチコア環境でもスケールするためのデータ構造として、CPU の特別な命令セットである CAS 命令を設計のコアに据え、Mapping Table と呼ばれる中間キャッシュレイヤーを実装した Buzzword-Tree の革新的なアーキテクチャについて触れました。

そのほか Bookclub で盛り上がった観点や、次回の Chapter 7 の予定について触れました。

ご意見・ご感想など、お便りはこちらの⁠⁠⁠⁠⁠⁠⁠ ⁠⁠⁠Google Form⁠⁠⁠⁠⁠⁠⁠⁠⁠⁠ で募集しています。