概要

• データベース をゼロから構築する方法の解説
• ファイルベース のシンプルなKey-Valueストアから始める流れ
• 更新・削除の非効率性 とその対策としての「追記専用ファイル」戦略
• インデックス導入 による検索高速化とメモリ・パフォーマンスのトレードオフ
• ソート済みデータ構造 と耐障害性のための仕組みを紹介

Key-Valueデータベースの自作入門

• Key-Valueデータベース は、JavaScriptのオブジェクトのように キー で値を保存・取得する仕組み
• データの 永続化 と 効率的な検索 が主な課題
• 最も単純な方法は ファイル を使い、キーと値のペアを順次保存する方式

ファイルベースKey-Valueストアの基本操作

• データの保存：db set 1 "Lorem ipsum" のようにファイルへ追記
• データの検索：ファイル内の全ペアを 逐次検索
• データの更新・削除：対象レコードを見つけて その場で書き換え・削除

問題点と改善策

• 更新・削除時 に後続データの移動が発生し、 大規模化で非効率
• 追記専用（Append-Only）方式へ移行し、 既存データは不変 とする
  • 更新や削除は 新たなレコード や「削除マーク（tombstone）」を末尾に追記
  • これにより、 データ移動のコスト削減

ファイル肥大化とコンパクション

• 追記専用 方式では、不要なデータや削除済みデータも残り、 ファイルサイズが無限に増加
• 一定サイズで セグメント（分割ファイル） を作成し、新規データは新セグメントへ
• 古いセグメント は「コンパクション（圧縮）」で 有効なレコードのみ残して縮小
• セグメントの 統合 も可能で、ストレージの効率化を実現

検索高速化のためのインデックス

• ファイル全体を 逐次検索 するのは非効率
• インメモリのハッシュテーブル などをインデックスとして利用し、 キーとファイル内オフセット を管理
  • キー検索時はインデックスからオフセットを引き、 直接ファイルを参照
• セグメントごとに インデックス が必要
• インデックスの更新は 書き込み速度低下 のトレードオフ

インメモリとオンディスクの違い

• インメモリ は高速だがプログラム終了でデータ消失
• オンディスク は永続化できるが、 アクセス速度は低下
• インデックスは メモリ使用量 と 検索速度 のバランスが重要

ソート済みデータ構造とスパースインデックス

• ソート済み データにより、範囲検索やスパースインデックス（間引きインデックス）が可能
• ソートされていれば、一部のキーのみインデックス化しても 効率的な探索 が可能
• インデックス密度 を調整することで、 メモリ消費と検索速度 のトレードオフが可能

ソートと永続性の両立

• データを 常にソート するのはディスク上では非効率
• 解決策： インメモリでソート済みリスト に追加し、一定サイズで ソート済みファイル としてディスクへ書き出し
  • インメモリリストには バランス木やスキップリスト などを利用
  • 書き出し時に インデックスも生成
• インメモリリストは クラッシュ時に消失 するため、追加ごとに 追記専用ログ へ保存し耐障害性を確保

まとめ：自作Key-Valueデータベースの流れ

• 新規データ はインメモリのソート済みリストへ追加、同時にログファイルへ追記
• リストが大きくなったら ソート済みファイル としてディスクへフラッシュし、インデックスを作成
• 検索時はまずインメモリリスト、次にインデックスを使ってディスクファイルを参照
• ディスク上のファイルは 不変（immutable） とし、更新・削除は新規レコード追記で対応
• 定期的な コンパクション で不要データを除去し、ファイルサイズを抑制

このようにして、 シンプルかつ効率的なKey-Valueデータベース を自作可能。実際の商用DB（例: LevelDB, RocksDB, Redisなど）も、この基本構造を発展させている。