ストレージとインデックス

データベースはどうデータを保存するか

データベースの核心は「書き込んだデータをあとで効率よく読み出す」ことです。 この目的のために、ストレージエンジンはインデックス（索引）を維持します。 『データ指向アプリケーションデザイン』第 3 章では、代表的なインデックス構造として B-tree と LSM-tree を比較しています。

B-tree

B-tree は、ほとんどのリレーショナルデータベース（PostgreSQL、MySQL InnoDB）が採用する読み取り最適化の構造です。 データを固定サイズのページに分割し、木構造で管理するため、ランダムリードが O(log n) で完了します。 書き込み時はページの上書きが必要なため、クラッシュ対策として先行書き込みログ（WAL: Write-Ahead Log） を併用します。

-- PostgreSQL の B-tree インデックス作成例
CREATE INDEX idx_users_email ON users (email);

-- 実行計画でインデックスが使われていることを確認
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'test@example.com';

LSM-tree

LSM-tree（Log-Structured Merge-tree） は、Cassandra や RocksDB が採用する書き込み最適化の構造です。 書き込みはまずメモリ上のメムテーブルに蓄積され、一定サイズに達するとSSTable（Sorted String Table） としてディスクに書き出されます。 読み取り時は複数の SSTable をマージしながら検索するため、書き込みが高速な代わりに読み取りコストが高くなります。

# Cassandra でテーブル作成（LSM-tree ベースのストレージ）
cqlsh -e "
CREATE KEYSPACE demo WITH replication = {'class': 'SimpleStrategy', 'replication_factor': 1};
CREATE TABLE demo.events (
    event_id UUID PRIMARY KEY,
    event_type TEXT,
    payload TEXT,
    created_at TIMESTAMP
);
"

ハッシュインデックス

ハッシュインデックスは、キーのハッシュ値からディスク上のオフセットを直接引く方式です。 Bitcask（Riak のデフォルトエンジン）がこの方式を採用しており、すべてのキーがメモリに収まる場合に極めて高速です。 範囲検索ができないという制約があるため、用途は限定されます。

読み取り最適化 vs 書き込み最適化

ワークロードの読み書き比率を見極め、適切なストレージエンジンを選ぶことが設計の出発点です。