世紀末LSM-Treeプチフリ神話の終わり - Software Transactional Memo

凍った木が溶け始める様子をそれっぽく描いてもらった この記事はデータベース・システム系 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の典型的な実装の概要とその利点・欠点を整理すると

[yarumato]

“LSM-Treeはデータ構造としては順序付きの辞書。その一種、LevelDBはChromiumでも使われている。利点・欠点を整理。メモリに入り切らない総量の順序ありデータを効率的に探索できる。大きな欠点は応答時間のスパイク”