目次を表示する

CS基礎：計算量とデータ構造

B-Tree / LSM-Tree / Skip List ── データベースの内部構造

B-Tree / LSM-Tree / Skip List ── データベースの内部構造

扱う概念：B-Tree（多方向平衡木）、LSM-Tree（Log-Structured Merge-Tree）、Skip List、WAL、MemTable / SSTable、コンパクション

DB内部構造 — B-Tree・LSM-Tree・Skip List

この章で何ができるようになるか：「RDB は B-Tree、NoSQL は LSM-Tree」という棲み分けの理由を内部構造から説明でき、Redis が Skip List を選んだ理由を理解できる。

なぜ専用のデータ構造が必要か

メモリ上の二分探索木は O(log n) で高速だが、データがディスクに載ると話が変わる。

メモリアクセス:  ~100 ns
SSD ランダム読み: ~100 μs（1000倍遅い）
HDD ランダム読み: ~10 ms（100,000倍遅い）

→ ディスクI/Oの回数を最小化するデータ構造が必要

B-Tree：ディスクI/Oに最適化された多方向木

RDB のインデックスの標準。PostgreSQL、MySQL (InnoDB) で使用。

B-Tree (order=4) の例:
            [10 | 20 | 30]
           /    |     |    \
     [3|5|7] [12|15] [22|25] [35|40|45]

特徴:
  - 1ノードに複数のキーを持つ（ディスクの1ブロックに収める）
  - 全葉ノードが同じ深さ（完全平衡）
  - ディスクの1ページ（4KB〜16KB）= 1ノード → I/O 1回で数百キーを読める

なぜ二分木ではなくB-Treeか

1000万件のデータを検索する場合:

二分木（AVL/Red-Black Tree）:
  高さ = log₂(10,000,000) ≈ 23
  → ディスクI/O 23回

B-Tree (order=500):
  高さ = log₅₀₀(10,000,000) ≈ 3
  → ディスクI/O 3回

差: 8倍のI/O削減
class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []
        self.leaf = leaf

class BTree:
    def __init__(self, order: int = 4):
        self.root = BTreeNode()
        self.order = order  # 最大子ノード数
        self.max_keys = order - 1

    def search(self, key, node=None) -> bool:
        if node is None:
            node = self.root

        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1

        if i < len(node.keys) and key == node.keys[i]:
            return True

        if node.leaf:
            return False

        return self.search(key, node.children[i])

    def insert(self, key):
        root = self.root
        if len(root.keys) == self.max_keys:
            # ルートが満杯 → 分割して新しいルートを作る
            new_root = BTreeNode(leaf=False)
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
        self._insert_non_full(self.root, key)

    def _insert_non_full(self, node, key):
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == self.max_keys:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            self._insert_non_full(node.children[i], key)

    def _split_child(self, parent, idx):
        """子ノードを半分に分割し、中央キーを親に持ち上げる"""
        child = parent.children[idx]
        mid = len(child.keys) // 2
        new_node = BTreeNode(leaf=child.leaf)

        # 中央キーを親に挿入
        parent.keys.insert(idx, child.keys[mid])
        parent.children.insert(idx + 1, new_node)

        # 右半分を新ノードに移動
        new_node.keys = child.keys[mid + 1:]
        child.keys = child.keys[:mid]

        if not child.leaf:
            new_node.children = child.children[mid + 1:]
            child.children = child.children[:mid + 1]

B+ Tree（B-Tree の変種）

実際の RDB では B-Tree ではなく B+ Tree が使われる。

B+ Tree の違い：
  - データは葉ノードにのみ格納（内部ノードはキーとポインタのみ）
  - 葉ノード同士がリンクリストで連結 → 範囲検索が高速

内部ノード: [10 | 20 | 30] → キーのみ（データなし）
葉ノード:   [3→5→7→10] → [12→15→18→20] → [22→25→28→30]
                          リンクリストで連結

LSM-Tree：書き込みに最適化された構造

Cassandra、RocksDB、LevelDB、HBase で使用。

書き込みのボトルネック:
  B-Tree: 更新のたびにディスク上のノードをランダムアクセスで書き換え
  LSM-Tree: メモリに書いてバッチでディスクに書き出す（シーケンシャルI/O）
LSM-Tree の構成:
  WAL (Write-Ahead Log)  → クラッシュ復旧用のログ
  MemTable (メモリ)       → Red-Black Tree や Skip List で実装
  SSTable (ディスク)      → ソート済み・不変のファイル群
class LSMTree:
    """LSM-Tree の概念実装"""

    def __init__(self, memtable_threshold: int = 1000):
        self.wal = []               # Write-Ahead Log
        self.memtable = {}          # メモリ上のソート済みマップ
        self.sstables = []          # ディスク上のSSTableリスト（レベル別）
        self.threshold = memtable_threshold

    def put(self, key: str, value: str):
        # 1. WAL に書く（クラッシュ復旧用）
        self.wal.append(("PUT", key, value))
        # 2. MemTable に書く
        self.memtable[key] = value
        # 3. MemTable が閾値を超えたらフラッシュ
        if len(self.memtable) >= self.threshold:
            self._flush()

    def get(self, key: str) -> str | None:
        # 1. MemTable を検索（最新のデータ）
        if key in self.memtable:
            return self.memtable[key]
        # 2. SSTable を新しい順に検索
        for sstable in reversed(self.sstables):
            if key in sstable:
                return sstable[key]
        return None

    def _flush(self):
        """MemTable をソートしてSSTableとしてディスクに書き出す"""
        sorted_data = dict(sorted(self.memtable.items()))
        self.sstables.append(sorted_data)
        self.memtable = {}
        self.wal = []
        # SSTableが増えすぎたらコンパクション
        if len(self.sstables) > 4:
            self._compact()

    def _compact(self):
        """複数のSSTableをマージして1つにする"""
        merged = {}
        for sstable in self.sstables:
            merged.update(sstable)  # 新しいSSTableが上書き（最新が優先）
        self.sstables = [dict(sorted(merged.items()))]

B-Tree vs LSM-Tree

B-TreeLSM-Tree
読み取り速い（1回のツリー探索）遅い（MemTable→複数SSTable）
書き込み遅い（ランダムI/O）速い（シーケンシャルI/O）
空間効率△ 断片化する✅ コンパクションで最適化
使用例PostgreSQL, MySQLCassandra, RocksDB, LevelDB
向いているパターン読み多・書き少書き多・読み少

Skip List：確率的平衡データ構造

Redis の Sorted Set の内部実装。

Skip List の構造（レベル付きリンクリスト）:

Level 3:  HEAD ────────────────────────────── 50 ──── NIL
Level 2:  HEAD ──────── 20 ─────────────────── 50 ──── NIL
Level 1:  HEAD ── 10 ── 20 ── 30 ── 40 ── 50 ── NIL
Level 0:  HEAD ── 10 ── 20 ── 30 ── 40 ── 50 ── NIL  (全要素)

検索「35」:
  Level 3: HEAD → 50（大きすぎる）→ 1段下がる
  Level 2: HEAD → 20 → 50（大きすぎる）→ 1段下がる
  Level 1: 20 → 30 → 40（大きすぎる）→ 1段下がる
  Level 0: 30 → 40 → 35は存在しない

→ 平均 O(log n)（レベルの高さが log n に収まる確率が高い）
import random

class SkipListNode:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)

class SkipList:
    MAX_LEVEL = 16
    P = 0.5  # レベルアップの確率

    def __init__(self):
        self.header = SkipListNode(float('-inf'), self.MAX_LEVEL)
        self.level = 0

    def _random_level(self) -> int:
        lvl = 0
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def insert(self, key):
        update = [None] * (self.MAX_LEVEL + 1)
        current = self.header

        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current

        new_level = self._random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.header
            self.level = new_level

        new_node = SkipListNode(key, new_level)
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

    def search(self, key) -> bool:
        current = self.header
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        current = current.forward[0]
        return current is not None and current.key == key

なぜ Redis は Skip List を選んだか

Redis の作者 Salvatore Sanfilippo の説明：

1. 実装がシンプル（AVL/Red-Black Tree より簡単にバグなく書ける）
2. 範囲クエリが得意（ZRANGEBYSCORE: ノードを順にたどるだけ）
3. レベル調整がローカル（回転操作のようなグローバルな再構築が不要）
4. 平均性能がバランス木と同等（定数倍の差はあるが実用上問題ない）

まとめ

データ構造読み取り書き込み空間主な使用例
B-TreeO(log n)O(log n)△RDBMS インデックス
B+ TreeO(log n) + 範囲◎O(log n)△PostgreSQL, InnoDB
LSM-TreeO(log n) × levelsO(1) 償却✅Cassandra, RocksDB
Skip ListO(log n) 平均O(log n) 平均O(n log n)Redis Sorted Set