データベースの基礎

データベースの基礎

執筆済 ソフトウェア開発データベース

保存の仕組み#

DB は最終的にディスク上のファイルに書く。 違いはどう構造化するか。

構造 特徴 例
B木 / B+木 読みが速い。更新は所定の位置へ PostgreSQL、MySQL、SQLite
LSM 木 書きが速い。追記中心 RocksDB、Cassandra
ハッシュ 完全一致のみ Redis

B木は「読み最適化」、LSM は「書き最適化」。 どちらが良いかは負荷の性質による。

行指向と列指向#

行指向 列指向
保存 1 行分をまとめて 1 列分をまとめて
適する OLTP（1 件の読み書き） OLAP（大量の集計）
圧縮 効きにくい 効きやすい（同種の値が並ぶ）
例 PostgreSQL、MySQL ClickHouse、BigQuery

「1 億行の売上を月別に集計する」場合、 行指向は不要な列まで読むことになる。

ページとバッファプール#

ディスクは 4〜16 KB のページ単位で読み書きする。 よく使うページをメモリに保持するのがバッファプール。

DB の性能はほぼキャッシュヒット率で決まる。 メモリに乗り切るデータ量なら劇的に速い。 CPU のキャッシュと 同じ構造が、階層を変えて現れている。

WAL#

変更を先にログに書き、後で本体に反映する。

1. 変更内容をログに追記して fsync
2. コミット完了を返す
3. 実際のページは後でまとめて書く
  • 追記なのでディスクへの書き込みが順次になり速い
  • 途中で落ちてもログから復旧できる

ジャーナリング FS と 同じ発想。

参考文献#

  • Martin Kleppmann. Designing Data-Intensive Applications. O’Reilly, 2017.
  • Raghu Ramakrishnan, Johannes Gehrke. Database Management Systems, 3rd ed. McGraw-Hill, 2003.
  • Alex Petrov. Database Internals. O’Reilly, 2019.