凍った木が溶け始める様子をそれっぽく描いてもらった この記事はデータベース・システム系 Advent Calendar 2023の2日目の記事である。前日は僕、明日も僕。 Log Structured Merge Tree(以下LSM-Tree)という物をご存知だろうか。データ構造としては順序付きの辞書であり結構昔に発明されており各操作の計算オーダーは赤黒木等と同じである。システム系学会を追っていると無限に亜種が提案されているので特徴を一言で言い表すのは難しいのだが、その一種であるLevelDBはChromiumの中でも使われている。 https://chromium.googlesource.com/chromium/src/+/HEAD/third_party/leveldatabase/leveldb_chrome.h LSM-Treeの典型的な実装の概要とその利点・欠点を整理すると