0%
💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.
目次
1. はじめに：なぜデータベース内部構造を知るべきか
データベースは現代（げんだい）ソフトウェアシステムの心臓（しんぞう）です。単純（たんじゅん）にSQLクエリを書くことを超（こ）え、内部（ないぶ）でデータがどのように保存（ほぞん）・検索（けんさく）されるかを理解（りかい）すれば、パフォーマンス問題（もんだい）を根本的（こんぽんてき）に解決（かいけつ）できます。
このガイドで扱（あつか）う主要（しゅよう）トピック：
- ストレージエンジンの2つのパラダイム：ページ指向（しこう）（B-Tree）vs ログ構造（こうぞう）（LSM-Tree）
- Buffer Poolとキャッシュ戦略（せんりゃく）
- WAL（Write-Ahead Log）と障害（しょうがい）復旧（ふっきゅう）
- MVCCとトランザクション分離（ぶんり）レベル
- ロックメカニズムとデッドロック
- クエリオプティマイザの動作原理（どうさげんり）
- InnoDB、RocksDB内部構造
データベース内部構造 全体アーキテクチャ
============================================
Client Query
|
v
[SQL Parser] --> [Query Optimizer] --> [Execution Engine]
| |
v v
[Buffer Pool / Cache] [Transaction Manager]
| |
v v
[Storage Engine] [Lock Manager + MVCC]
|
+---> [B-Tree Index] (ページ指向)
+---> [LSM-Tree] (ログ構造)
|
v
[WAL (Write-Ahead Log)]
|
v
[Disk (データファイル + ログファイル)]
2. ストレージエンジン概要：ページ指向 vs ログ構造
ストレージエンジンは、データをディスクに保存（ほぞん）し読（よ）み出（だ）す中核（ちゅうかく）コンポーネントです。大（おお）きく2つのパラダイムが存在（そんざい）します。
2.1 ページ指向ストレージ（Page-Oriented）
伝統的（でんとうてき）なRDBMSが採用（さいよう）する方式（ほうしき）です。固定（こてい）サイズのページ（通常（つうじょう）4KB〜16KB）単位（たんい）でデータを管理（かんり）します。
ページ指向ストレージ構造
========================
[Page 0: File Header]
[Page 1: B-Tree Root]
[Page 2: B-Tree Internal]
[Page 3: B-Tree Leaf (data)]
[Page 4: B-Tree Leaf (data)]
[Page 5: Free Space Map]
...
[Page N: B-Tree Leaf (data)]
各ページの内部構造:
+----------------------------------+
| Page Header (LSN, checksum, ...) |
| Slot Array (オフセットポインタ) |
| ...free space... |
| Tuple 3 | Tuple 2 | Tuple 1 |
+----------------------------------+
特徴（とくちょう）：
- 読（よ）み取（と）り最適化（さいてきか）：インデックスによる高速（こうそく）ポイントクエリ
- In-place更新（こうしん）：保存場所（ほぞんばしょ）で直接（ちょくせつ）データを修正（しゅうせい）
- 代表的（だいひょうてき）な実装（じっそう）：MySQL InnoDB、PostgreSQL、SQL Server、Oracle
2.2 ログ構造ストレージ（Log-Structured）
すべての書（か）き込（こ）みを順次（じゅんじ）ログとして記録（きろく）する方式です。書き込みパフォーマンスに最適化されています。
ログ構造ストレージ アーキテクチャ
=================================
Write Path:
[Client Write] --> [MemTable (in-memory, sorted)]
|
(flush when full)
|
v
[SSTable L0] (immutable, sorted)
[SSTable L0]
|
(compaction)
|
v
[SSTable L1] (merged, sorted)
|
(compaction)
|
v
[SSTable L2] (larger, sorted)
特徴：
- 書き込み最適化：順次書き込みのみで高いスループットを実現
- 読み取り時に複数のSSTableを確認する必要がある場合あり
- 代表的な実装：RocksDB、LevelDB、Cassandra、HBase
2.3 比較まとめ
| 特性 | ページ指向（B-Tree） | ログ構造（LSM-Tree） |
|---|---|---|
| 書き込み性能 | 普通（ランダムI/O） | 優秀（シーケンシャルI/O） |
| 読み取り性能 | 優秀（インデックス直接アクセス） | 普通（複数レベル探索） |
| 空間効率 | 普通（ページ内断片化） | 優秀（コンパクションで整理） |
| 書き込み増幅 | 低い | 高い（コンパクション） |
| 読み取り増幅 | 低い | 高い（複数SSTable） |
| 代表DB | MySQL、PostgreSQL | RocksDB、Cassandra |
3. B-Tree深掘り分析
B-Treeは1972年にRudolf BayerとEdward McCreightが発明（はつめい）した自己均衡木（じこきんこうぎ）データ構造です。ほぼすべてのRDBMSインデックスの基盤（きばん）となっています。
3.1 B-Tree基本構造
B-Tree構造 (order = 4)
========================
[ 30 | 60 ] <-- Root Node
/ | \
v v v
[10|20] [40|50] [70|80|90] <-- Internal Nodes
/ | \ / | \ / | | \
v v v v v v v v v v
[1] [15] [25] [35] [45] [55] [65] [75] [85] [95] <-- Leaf Nodes
5 17 28 38 48 58 68 78 88 98
8 19 39 59 79 99
B-Treeの属性（ぞくせい）（order = m）：
- ルートは最低（さいてい）2つの子（こ）を持（も）つ
- 内部（ないぶ）ノードはceil(m/2)〜m個（こ）の子を持つ
- すべてのリーフノードは同（おな）じ深（ふか）さに位置（いち）
- 検索・挿入・削除：O(log N)
3.2 ノード分割（Node Splitting）
ノードが満杯（まんぱい）になると分割（ぶんかつ）が発生（はっせい）します。
ノード分割プロセス (order = 4, キー25を挿入)
=============================================
Before:
Parent: [20 | 40]
Child: [21 | 23 | 24] (full!)
Step 1: 25を挿入するとoverflow
Temp: [21 | 23 | 24 | 25]
Step 2: 中間値(23)を親に昇格
Parent: [20 | 23 | 40]
Left: [21]
Right: [24 | 25]
After:
[20 | 23 | 40]
/ | | \
... [21] [24|25] ...
3.3 B+Tree vs B-Tree
ほとんどのデータベースは純粋（じゅんすい）なB-Treeではなく、B+Treeを使用（しよう）します。
B+Tree構造
============
Internal Nodes: キーのみ保存（データなし）
[30 | 60]
/ | \
v v v
Leaf: [10|20|30] --> [40|50|60] --> [70|80|90]
data data data
主な違い:
- B-Tree: すべてのノードにデータを保存
- B+Tree: リーフノードにのみデータを保存
- B+Tree: リーフノードが連結リストで接続（範囲スキャン最適化）
B+Treeの利点（りてん）：
- 内部ノードにより多くのキーを格納可能（fanout増加）
- 範囲（はんい）クエリ時にリーフノードを順次（じゅんじ）走査（そうさ）
- より一貫（いっかん）した検索パフォーマンス（常にリーフまで辿る）
3.4 クラスタードvsノンクラスタードインデックス
クラスタードインデックス（InnoDB Primary Key）
==============================================
B+Treeリーフ = 実際のテーブルデータ
[PK: 1] --> {id:1, name:'Alice', age:30}
[PK: 2] --> {id:2, name:'Bob', age:25}
[PK: 3] --> {id:3, name:'Carol', age:35}
ノンクラスタードインデックス（Secondary Index）
================================================
B+Treeリーフ = プライマリキー参照
[name:'Alice'] --> PK: 1 (クラスタードインデックスの再検索が必要！)
[name:'Bob'] --> PK: 2
[name:'Carol'] --> PK: 3
クラスタードインデックスの特徴：
- テーブルごとに1つのみ（通常PK）
- データがPK順（じゅん）で物理的（ぶつりてき）にソート
- 範囲クエリに非常（ひじょう）に効率的（こうりつてき）
ノンクラスタードインデックスの二重検索問題：
- Secondary Index検索後、クラスタードインデックスを再検索する必要がある
- これを「bookmark lookup」または「table lookup」と呼ぶ
- Covering Indexで回避（かいひ）可能
4. LSM-Tree深掘り分析
LSM-Tree（Log-Structured Merge Tree）は書き込み集中（しゅうちゅう）ワークロードに最適化されたデータ構造です。
4.1 LSM-Treeアーキテクチャ
LSM-Tree全体構造
==================
[Write Request]
|
v
[WAL (ディスク)] <--- 障害復旧用の先行記録
|
v
[MemTable (メモリ)] <--- Red-Black TreeまたはSkip List
|
(MemTableが閾値に到達)
|
v
[Immutable MemTable]
|
(ディスクにflush)
|
v
[Level 0 SSTables] <--- キー範囲の重複あり
|
(Compaction)
|
v
[Level 1 SSTables] <--- キー範囲の重複なし
|
(Compaction)
|
v
[Level 2 SSTables] <--- より大きなファイル
|
...
4.2 MemTable
MemTableはメモリに常駐（じょうちゅう）するソート済みデータ構造です。
// MemTable実装例（Skip Listベース）
class MemTable {
private final ConcurrentSkipListMap<byte[], byte[]> data;
private final AtomicLong approximateSize;
private static final long FLUSH_THRESHOLD = 64 * 1024 * 1024; // 64MB
public void put(byte[] key, byte[] value) {
data.put(key, value);
approximateSize.addAndGet(key.length + value.length);
}
public byte[] get(byte[] key) {
return data.get(key);
}
public boolean shouldFlush() {
return approximateSize.get() >= FLUSH_THRESHOLD;
}
// MemTable -> SSTable変換
public SSTable flush(String sstablePath) {
SSTableBuilder builder = new SSTableBuilder(sstablePath);
for (Map.Entry<byte[], byte[]> entry : data.entrySet()) {
builder.add(entry.getKey(), entry.getValue());
}
return builder.build(); // ソート済み状態でディスクに記録
}
}
4.3 SSTable（Sorted String Table）
SSTable内部構造
================
+-------------------------------------------+
| Data Block 0 |
| key1:value1 | key2:value2 | key3:value3 |
+-------------------------------------------+
| Data Block 1 |
| key4:value4 | key5:value5 | key6:value6 |
+-------------------------------------------+
| ... |
+-------------------------------------------+
| Meta Block (Bloom Filter) |
+-------------------------------------------+
| Index Block |
| block0_last_key -> offset0 |
| block1_last_key -> offset1 |
+-------------------------------------------+
| Footer |
| index_offset | meta_offset | magic_num |
+-------------------------------------------+
4.4 コンパクション戦略
Size-Tiered Compaction（STCS）
Size-Tiered Compaction
======================
サイズが似たSSTableを合併
Level 0: [T1] [T2] [T3] [T4] (各64MB)
|
(4つ溜まったら合併)
|
v
Level 1: [ T1+T2+T3+T4 ] (約256MB)
利点: 書き込み増幅が低い
欠点: 空間増幅が高い（一時的に2倍の空間が必要）
読み取り時に複数のSSTableを確認する必要あり
Leveled Compaction（LCS）
Leveled Compaction
==================
各レベルはキー範囲が重複しないSSTableで構成
Level N+1のサイズはLevel Nの10倍
L0: [a-z] [a-z] [a-z] (キー範囲重複許可, 各64MB)
|
L1: [a-e] [f-k] [l-p] [q-z] (キー範囲重複なし, 合計640MB)
|
L2: [a-b] [c-d] ... [y-z] (キー範囲重複なし, 合計6.4GB)
利点: 読み取り増幅が低い、空間増幅が低い
欠点: 書き込み増幅が高い（レベルあたり最大10倍）
4.5 Bloom Filter
Bloom Filterは、SSTableに特定のキーが存在するかどうかを高速に判断する確率的データ構造です。
# Bloom Filterの動作原理
class BloomFilter:
def __init__(self, size, num_hash_functions):
self.bit_array = [0] * size
self.size = size
self.num_hash = num_hash_functions
def add(self, key):
for i in range(self.num_hash):
index = hash(key, seed=i) % self.size
self.bit_array[index] = 1
def might_contain(self, key):
"""
True -> キーが存在する可能性あり（偽陽性あり）
False -> キーが確実に存在しない（偽陰性なし）
"""
for i in range(self.num_hash):
index = hash(key, seed=i) % self.size
if self.bit_array[index] == 0:
return False
return True
4.6 書き込み増幅（Write Amplification）
書き込み増幅分析
=================
元データ: 1 byte
B-Tree書き込み増幅:
WAL記録(1) + ページ書き込み(1) = 約2倍
（実際にはページサイズ分書き込む場合もありさらに高い）
LSM-Tree書き込み増幅（Leveled Compaction）:
WAL記録(1) + MemTable flush(1) + L0->L1(10) + L1->L2(10) + ...
= 約10 x レベル数
例: 5レベルの場合、約50倍の書き込み増幅！
5. Buffer Pool管理
Buffer Poolはディスクページをメモリにキャッシュする中核コンポーネントです。
5.1 Buffer Poolアーキテクチャ
Buffer Pool構造
================
[Hash Table: page_id -> frame_id]
|
v
+------+------+------+------+------+
|Frame0|Frame1|Frame2|Frame3|Frame4| <-- Buffer Pool (メモリ)
|Page5 |Page12|Page3 |empty |Page8 |
|dirty |clean |dirty | |clean |
+------+------+------+------+------+
[Free List]: [Frame3]
[LRU List]: Frame4 <-> Frame1 <-> Frame0 <-> Frame2
(least) (most)
5.2 ページ置換アルゴリズム
LRU（Least Recently Used）
class LRUReplacer:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def access(self, frame_id):
if frame_id in self.cache:
self.cache.move_to_end(frame_id)
else:
if len(self.cache) >= self.capacity:
self.cache.popitem(last=False) # 最も古いものを削除
self.cache[frame_id] = True
def evict(self):
if self.cache:
frame_id, _ = self.cache.popitem(last=False)
return frame_id
return None
Clockアルゴリズム（Second Chance）
Clockアルゴリズム
=================
時計の針が循環しながら置換対象のフレームを探す
[Frame0: ref=1]
/ \
[Frame4: ref=0] [Frame1: ref=1] <-- clock hand位置
\ /
[Frame3: ref=1]
|
[Frame2: ref=0]
置換プロセス:
1. clock handが指すFrame1のref bitを確認
2. ref=1ならref=0に設定して次へ移動
3. ref=0のフレームを見つけたら置換対象に選択
4. Frame2(ref=0)を置換対象として選択
5.3 Dirty PageとCheckpoint
Checkpointプロセス
==================
1. Dirty Page一覧を収集
Frame0(Page5): dirty -> ディスクへの書き込みが必要
Frame2(Page3): dirty -> ディスクへの書き込みが必要
2. Fuzzy Checkpoint（InnoDB方式）
- すべてのdirty pageを一度に書き込まない
- バックグラウンドで段階的に記録
- システム負荷を分散
3. Checkpoint LSNを記録
- このLSN以前のWALログは復旧時に不要
- WALファイルを再利用可能
Timeline:
WAL: [LSN:100][LSN:101]...[LSN:200][LSN:201]...
^
Checkpoint LSN=200
(LSN 200以前の変更はすべて安全にディスクに記録済み)
6. WAL（Write-Ahead Log）深掘り分析
WALはデータ変更前にログを先に記録するプロトコルです。障害復旧の根幹です。
6.1 WALの動作原理
WAL記録フロー
=============
1. トランザクション開始
BEGIN;
2. UPDATE users SET name='Bob' WHERE id=1;
a) WALにログレコードを記録:
[LSN:101, TxID:5, Table:users, PK:1,
old:{name:'Alice'}, new:{name:'Bob'}]
b) Buffer Pool内のページを修正（メモリ上のみ）
3. COMMIT;
a) WALにコミットレコードを記録:
[LSN:102, TxID:5, COMMIT]
b) WALをディスクにfsync（これがCOMMITの永続性を保証！）
c) クライアントに成功応答
核心: データページは後から遅延的にディスクに書き込まれる
WALさえディスクにあれば障害後の復旧が可能
6.2 Log Sequence Number（LSN）
LSNの構造と役割
================
WAL File:
[LSN:100|INSERT|TxID:3|...][LSN:101|UPDATE|TxID:5|...][LSN:102|COMMIT|TxID:5]
Buffer Pool Page Header:
+------------------+
| Page LSN: 101 | <-- このページに最後に適用されたWALレコード
| Checksum: 0xAB12 |
| ... |
+------------------+
Checkpoint LSN: 100
-> LSN 100以前の変更はすべてディスクに反映済み
-> 復旧時はLSN 100以降からredo（再実行）
Flushed LSN: 102
-> WALファイルでディスクに記録された最後のLSN
6.3 Group Commit
Group Commit最適化
==================
個別fsyncは非常にコストが高い（SSDでも数百マイクロ秒）
Group Commitなし:
Tx1: write WAL -> fsync -> respond (10ms)
Tx2: write WAL -> fsync -> respond (10ms)
Tx3: write WAL -> fsync -> respond (10ms)
合計: 30ms, 3回のfsync呼び出し
Group Commitあり:
Tx1: write WAL --|
Tx2: write WAL --|--> single fsync -> respond to all
Tx3: write WAL --|
合計: 10ms, 1回のfsync呼び出し
効果: fsync回数を大幅に削減し、スループットを大幅向上
6.4 障害復旧（Crash Recovery）
ARIES復旧プロトコル（Analysis-Redo-Undo）
==========================================
Phase 1: Analysis（分析）
WALを最初からスキャンして:
- 障害時点のアクティブトランザクション一覧を把握
- dirty page一覧を把握
Phase 2: Redo（再実行）
Checkpoint LSN以降のすべてのWALレコードを再実行
- コミット済みトランザクションの変更を復元
- 未コミットトランザクションの変更も一旦復元
Phase 3: Undo（取消）
未コミットトランザクションの変更を逆順で取り消し
例:
WAL: [Tx1:INSERT][Tx2:UPDATE][Tx1:COMMIT][Tx2:DELETE][CRASH!]
^
Analysis: Tx1=committed, Tx2=active(uncommitted)
Redo: Tx1のINSERTを再実行、Tx2のUPDATE/DELETEも再実行
Undo: Tx2のDELETEを取消、Tx2のUPDATEを取消
7. MVCC（多版本同時実行制御）
MVCCはデータの複数バージョンを維持（いじ）し、読み取りと書き込みが互（たが）いにブロックしないようにする同時実行制御技法（ぎほう）です。
7.1 PostgreSQL MVCC: xmin/xmax
PostgreSQL MVCC実装
=====================
各タプル（行）にメタデータを含む:
Tuple Header:
+----------+----------+--------+
| xmin | xmax | data |
+----------+----------+--------+
xmin: このタプルを作成（INSERT）したトランザクションID
xmax: このタプルを削除（DELETE/UPDATE）したトランザクションID（0なら有効）
例: UPDATE users SET age=31 WHERE id=1;
Before (xmin=100, xmax=0):
+----------+----------+-------------------+
| xmin=100 | xmax=0 | id=1, age=30 | <-- 現在のバージョン
+----------+----------+-------------------+
After (Tx 200がUPDATE実行):
+----------+----------+-------------------+
| xmin=100 | xmax=200 | id=1, age=30 | <-- 以前のバージョン（soft delete）
+----------+----------+-------------------+
+----------+----------+-------------------+
| xmin=200 | xmax=0 | id=1, age=31 | <-- 新バージョン
+----------+----------+-------------------+
7.2 MySQL InnoDB MVCC: Read View
InnoDB Read View構造
=====================
Read View作成時点のスナップショット:
{
creator_trx_id: 200, // 現在のトランザクションID
trx_ids: [150, 180], // 作成時点のアクティブトランザクション一覧
up_limit_id: 150, // trx_idsの最小値
low_limit_id: 201 // 次に割り当てられるトランザクションID
}
Undo Logを通じたバージョンチェーン:
Current Row: {id:1, name:'Carol', trx_id:200}
|
v (undo log pointer)
Undo v1: {id:1, name:'Bob', trx_id:180}
|
v (undo log pointer)
Undo v2: {id:1, name:'Alice', trx_id:100}
可視性判断:
- trx_id=200（creator）: 自身が修正 -> 可視
- trx_idがup_limit_id(150)未満: コミット確定 -> 可視
- trx_idがlow_limit_id(201)以上: 未来のトランザクション -> 不可視
- trx_idがtrx_idsに含まれる: アクティブトランザクション -> 不可視
- その他: コミット済み -> 可視
8. トランザクション分離レベル
8.1 4つの分離レベル
分離レベルと許容される異常現象
===============================
分離レベル | Dirty Read | Non-Repeatable | Phantom Read
================== | ========== | ============== | ============
READ UNCOMMITTED | 許容 | 許容 | 許容
READ COMMITTED | 防止 | 許容 | 許容
REPEATABLE READ | 防止 | 防止 | 許容*
SERIALIZABLE | 防止 | 防止 | 防止
* MySQL InnoDBのREPEATABLE READはGap LockでPhantom Readも防止
8.2 異常現象の例
-- Dirty Read (READ UNCOMMITTED)
-- Tx1:
BEGIN;
UPDATE accounts SET balance = 500 WHERE id = 1; -- 元は1000
-- まだCOMMITしていない！
-- Tx2 (READ UNCOMMITTED):
SELECT balance FROM accounts WHERE id = 1;
-- 結果: 500 (コミットされていないデータを読み取った！)
-- Tx1:
ROLLBACK; -- 500は無効化
-- Tx2は誤ったデータに基づいて判断する可能性あり
-- Non-Repeatable Read (READ COMMITTED)
-- Tx1:
BEGIN;
SELECT balance FROM accounts WHERE id = 1;
-- 結果: 1000
-- Tx2:
BEGIN;
UPDATE accounts SET balance = 500 WHERE id = 1;
COMMIT;
-- Tx1:
SELECT balance FROM accounts WHERE id = 1;
-- 結果: 500 (同じトランザクション内で異なる結果！)
9. ロック（Lock）メカニズム
9.1 ロックの種類
InnoDBロックの種類
==================
1. Record Lock（レコードロック）
特定のインデックスレコードをロック
例: WHERE id = 5 -> id=5のレコードのみロック
2. Gap Lock（ギャップロック）
インデックスレコード間の間隔をロック
例: WHERE id BETWEEN 5 AND 10
-> (5, 10)間に新しいレコードの挿入を防止
3. Next-Key Lock（ネクストキーロック）
Record Lock + Gap Lock
例: WHERE id = 5
-> id=5レコード + 前のレコードとのギャップ
InnoDB REPEATABLE READのデフォルトロック方式
4. Intention Lock（インテンションロック）
テーブルレベルの意図表明
- IS（Intention Shared）: 行レベルSロックを取得する意図
- IX（Intention Exclusive）: 行レベルXロックを取得する意図
9.2 デッドロック検出
-- デッドロックシナリオ
-- Tx1:
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- Lock A
-- Tx2:
BEGIN;
UPDATE accounts SET balance = balance - 200 WHERE id = 2; -- Lock B
-- Tx1:
UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- Lock B待ち
-- Tx2:
UPDATE accounts SET balance = balance + 200 WHERE id = 1; -- Lock A待ち
-- DEADLOCK! Tx1 -> Lock B -> Tx2 -> Lock A -> Tx1
デッドロック検出: Wait-for Graph
================================
Tx1 ---waits for---> Tx2
^ |
| |
+---waits for--------+
サイクル発見！ -> コストが低いトランザクションをロールバック
InnoDB方式:
- Wait-for graphを定期的に検査
- サイクル発見時、undo logが少ないトランザクションをvictimとして選択
- ERROR 1213 (40001): Deadlock found when trying to get lock
10. クエリオプティマイザ
10.1 クエリ処理パイプライン
クエリ処理フロー
=================
SQL Query
|
v
[Parser] --> AST (Abstract Syntax Tree)
|
v
[Binder/Analyzer] --> テーブル/カラム存在確認、型検査
|
v
[Query Rewriter] --> ビュー展開、サブクエリ変換
|
v
[Optimizer] --> 最適実行計画を選択
|
+---> [Cost Estimator] --> 各計画のコスト推定
+---> [Plan Enumerator] --> 可能な実行計画を列挙
|
v
[Execution Engine] --> 実行計画に従いデータにアクセス
10.2 コストベース最適化
コスト推定要素
==============
1. I/Oコスト: ディスクから読み取るページ数
- Sequential I/O: 1.0（基本単位）
- Random I/O: 4.0（SSD）〜 40.0（HDD）
2. CPUコスト: タプル処理コスト
- 比較演算: 0.01
- ハッシュ計算: 0.02
3. メモリコスト: ソート、ハッシュテーブルなど
コスト公式例（簡略化）:
Total Cost = (pages * seq_page_cost) + (tuples * cpu_tuple_cost)
例: フルテーブルスキャン
pages = 1000, seq_page_cost = 1.0
tuples = 100000, cpu_tuple_cost = 0.01
Total = 1000 * 1.0 + 100000 * 0.01 = 2000
10.3 ジョインアルゴリズムとコスト
ジョインアルゴリズム比較
========================
1. Nested Loop Join
for each row r in R: -- |R|回の反復
for each row s in S: -- |S|回の反復
if r.key == s.key:
emit (r, s)
コスト: O(|R| * |S|)
適切: 小さなテーブル、インデックスがある場合
2. Hash Join
Phase 1 (Build):
for each row r in R:
hash_table[hash(r.key)] = r
Phase 2 (Probe):
for each row s in S:
if hash_table[hash(s.key)] exists:
emit (match, s)
コスト: O(|R| + |S|)
適切: 大量のテーブル、等価結合
3. Sort-Merge Join
Phase 1: RをキーでSort
Phase 2: SをキーでSort
Phase 3: ソート済みRとSをMerge
コスト: O(|R|log|R| + |S|log|S| + |R| + |S|)
適切: すでにソート済みデータ、範囲結合
11. InnoDB内部構造
11.1 InnoDBアーキテクチャ概要
InnoDBアーキテクチャ
====================
In-Memory:
+-------------------------------------------------------+
| Buffer Pool |
| [Data Pages] [Index Pages] [Undo Pages] [Lock Info] |
| [Adaptive Hash Index] |
| [Change Buffer] |
+-------------------------------------------------------+
| Log Buffer |
+-------------------------------------------------------+
On-Disk:
+----------------------------+----------------------------+
| System Tablespace | Redo Log Files |
| (ibdata1) | (ib_logfile0, ib_logfile1)|
| - Data Dictionary | - WAL records |
| - Doublewrite Buffer | |
| - Change Buffer | |
| - Undo Logs | |
+----------------------------+----------------------------+
| Per-Table Tablespace (.ibd files) |
| - Table Data + Index |
+--------------------------------------------------------+
11.2 Change Buffer
Change Bufferの動作
===================
状況: Secondary IndexページがBuffer Poolにない場合
Change Bufferなし:
1. ディスクからページを読み込み（ランダムI/O！）
2. ページを修正
3. dirtyとしてマーク
Change Bufferあり:
1. 変更をChange Bufferに記録（メモリ）
2. 後でページが読み込まれた時にmerge
効果: ランダムI/OをシーケンシャルI/Oに変換
適切: 書き込みが多くsecondary indexが多いワークロード
不適切: unique index（重複チェックが必要）
11.3 Adaptive Hash Index（AHI）
Adaptive Hash Index
====================
InnoDBが頻繁にアクセスされるB+Treeページに自動でハッシュインデックスを構築
通常のB+Treeアクセス: O(log N) - 3〜4回のページアクセス
AHIアクセス: O(1) - ハッシュテーブル直接参照
動作方式:
1. 特定インデックスパターンのアクセス頻度を監視
2. 閾値超過時に自動でハッシュインデックスを作成
3. パターンが変更されるとハッシュインデックスを自動再構築/削除
注意: ワークロードによっては逆にパフォーマンス低下の可能性あり
innodb_adaptive_hash_index = ON|OFF
11.4 Doublewrite Buffer
Doublewrite Bufferの目的
========================
問題: Partial Page Write（Torn Page）
- OSページサイズ(4KB)とInnoDBページサイズ(16KB)が異なる
- 障害時に16KBページの一部のみ書き込まれる可能性
- WALでも復旧不可（WALはページの変更部分のみ記録）
解決: Doublewrite Buffer
1. dirty pageをまずdoublewrite buffer（連続領域）に記録
2. その後、実際の場所に記録
3. 障害時: doublewrite bufferから完全なページを復旧
フロー:
[Dirty Page] --> [Doublewrite Buffer (ディスク)] --> [実際のテーブルファイル]
(順次書き込み, 2MB単位) (ランダム書き込み)
12. RocksDB内部構造
12.1 RocksDBアーキテクチャ
RocksDBアーキテクチャ
======================
Write Path:
[Put/Delete] --> [WAL] --> [MemTable (Active)]
|
(switch when full)
|
v
[MemTable (Immutable)]
|
(background flush)
|
v
[L0 SST Files]
|
(background compaction)
|
v
[L1 SST Files]
|
...
|
v
[Ln SST Files]
Read Path:
[Get] --> [MemTable] --> [L0 SSTs] --> [L1 SSTs] --> ... --> [Ln SSTs]
(bloom) (bloom) (bloom) (bloom)
12.2 Column Families
Column Familiesの概念
======================
1つのDBインスタンス内で論理的に分離されたキーバリューネームスペース
CF "default": user:1 -> {"name":"Alice"}
CF "metadata": schema_version -> "3.2"
CF "timeseries": ts:1710000000 -> {"temp":23.5}
各Column Familyは独立した:
- MemTable
- SSTableセット
- Compaction設定
- Compression設定
12.3 Rate Limiter
Rate Limiter設定
=================
目的: コンパクションとフラッシュのI/Oを制限して
フォアグラウンドの読み書きパフォーマンスを保護
動作:
- コンパクション/フラッシュが100MB/s以上書き込まないよう制限
- フォアグラウンドリクエストがI/O帯域幅を確保できる
- ピーク時は低く、オフピーク時は高く動的調整可能
13. 実践パフォーマンスチューニングのヒント
13.1 インデックス最適化
-- カバリングインデックスで二重検索を排除
-- Before: secondary index -> clustered index (bookmark lookup)
SELECT name, email FROM users WHERE status = 'active';
-- index(status)のみではname, emailのためにテーブルアクセスが必要
-- After: カバリングインデックス
CREATE INDEX idx_status_covering ON users(status) INCLUDE (name, email);
-- インデックスのみでクエリ完了（Index Only Scan）
-- 複合インデックス順序の重要性（Leftmost Prefix Rule）
CREATE INDEX idx_abc ON orders(customer_id, order_date, status);
-- このインデックスを使用できるクエリ:
SELECT * FROM orders WHERE customer_id = 100; -- O
SELECT * FROM orders WHERE customer_id = 100 AND order_date > '2025-01-01'; -- O
-- このインデックスを使用できないクエリ:
SELECT * FROM orders WHERE order_date > '2025-01-01'; -- X
SELECT * FROM orders WHERE status = 'shipped'; -- X
13.2 Buffer Poolチューニング
# MySQL InnoDB Buffer Pool設定
[mysqld]
# メモリ全体の70-80%をBuffer Poolに割り当て
innodb_buffer_pool_size = 12G
# 複数インスタンスに分割して競合を軽減
innodb_buffer_pool_instances = 8
# Buffer Pool内容を再起動時に保存
innodb_buffer_pool_dump_at_shutdown = ON
innodb_buffer_pool_load_at_startup = ON
13.3 WAL/Redo Logチューニング
# InnoDB Redo Log設定
[mysqld]
# Redo logサイズ（小さすぎるとcheckpoint頻発、大きすぎると復旧時間増加）
innodb_redo_log_capacity = 4G
# fsync戦略
innodb_flush_log_at_trx_commit = 1 # 最も安全（デフォルト）
# = 0: 1秒ごとにfsync（最大1秒のデータ損失の可能性）
# = 1: コミットごとにfsync（最も安全、最も遅い）
# = 2: コミットごとにOSバッファに書き込み、1秒ごとにfsync
14. クイズ
データベース内部構造の理解度をチェックしましょう。
Q1. B+Treeでリーフノードが連結リストで接続されている理由は？
A: 範囲スキャン（Range Scan）の最適化のためです。例えば WHERE age BETWEEN 20 AND 30 のようなクエリで、B+Treeはage=20のリーフノードを見つけた後、連結リストに沿ってage=30まで順次スキャンできます。リーフノード間の接続がなければ、毎回ルートから再探索する必要があります。これがB+Treeが純粋なB-Treeより範囲クエリに効率的な核心的理由です。
Q2. LSM-TreeのLeveled Compactionで書き込み増幅が発生する理由は？
A: Leveled CompactionではLevel NのSSTableがLevel N+1に合併される際、Level N+1の重なるキー範囲に該当するすべてのSSTableを読み込み、マージして再書き込みする必要があります。Level N+1のサイズがLevel Nの約10倍であるため、1つのSSTableが最大10個のSSTableと合併される可能性があります。このプロセスが各レベルで繰り返されるため、全体の書き込み増幅は約10 x レベル数になります。
Q3. PostgreSQLでVACUUMが必要な理由をMVCCの観点から説明してください。
A: PostgreSQLのMVCCはUPDATEやDELETE時に以前のバージョンのタプルを即座に削除せず、xmaxを設定して「soft delete」処理します。こうして残った以前のバージョンを「dead tuple」と呼びます。時間が経つと、どのアクティブトランザクションも参照しないdead tupleが蓄積し、ディスク空間を浪費しインデックスパフォーマンスを低下させます。VACUUMはこれらのdead tupleを整理して空間を再利用可能にします。
Q4. InnoDBのNext-Key LockがPhantom Readを防止する原理を説明してください。
A: Next-Key LockはRecord LockとGap Lockの組み合わせです。例えば SELECT * FROM orders WHERE amount BETWEEN 100 AND 200 FOR UPDATE クエリでは、InnoDBは条件に該当するレコード自体（Record Lock）だけでなく、レコード間の間隔（Gap Lock）もロックします。これにより他のトランザクションがその範囲に新しい行を挿入できなくなり、Phantom Readが防止されます。
Q5. Buffer Poolのhit rateが低い場合（例: 90%）、どのような対策を取るべきですか？
A: Buffer Pool hit rateが低いということはディスクI/Oが頻繁に発生していることを意味します。対策としては：(1) innodb_buffer_pool_sizeを増やす（専用DBサーバーでは物理メモリの70-80%）。(2) 不要なフルテーブルスキャンを減らすためにクエリを最適化し、適切なインデックスを追加。(3) innodb_buffer_pool_instancesを増やしてmutex競合を軽減。(4) ワーキングセットがBuffer Poolより大きい場合、データパーティショニングやキャッシュレイヤー（Redis）を検討。目標は99%以上のhit rateです。
15. 参考資料
- Designing Data-Intensive Applications - Martin Kleppmann (O'Reilly, 2017)
- Database Internals - Alex Petrov (O'Reilly, 2019)
- MySQL Internals Manual - https://dev.mysql.com/doc/internals/en/
- PostgreSQL Documentation: MVCC - https://www.postgresql.org/docs/current/mvcc.html
- RocksDB Wiki - https://github.com/facebook/rocksdb/wiki
- InnoDB Buffer Pool - https://dev.mysql.com/doc/refman/8.0/en/innodb-buffer-pool.html
- B-Tree Visualizer - https://www.cs.usfca.edu/~galles/visualization/BTree.html
- The Log-Structured Merge-Tree (LSM-Tree) - Patrick O'Neil et al. (1996)
- ARIES: A Transaction Recovery Method - C. Mohan et al. (1992)
- Architecture of a Database System - Hellerstein, Stonebraker, Hamilton (2007)
- LevelDB Implementation Notes - https://github.com/google/leveldb/blob/main/doc/impl.md
- CMU Database Group Lectures - https://15445.courses.cs.cmu.edu/
- Use The Index, Luke - https://use-the-index-luke.com/
현재 단락 (1/754)
データベースは現代（げんだい）ソフトウェアシステムの心臓（しんぞう）です。単純（たんじゅん）にSQLクエリを書くことを超（こ）え、内部（ないぶ）でデータがどのように保存（ほぞん）・検索（けんさく）され...
작성 글자: 0자원문 글자: 20,925자작성 단락: 0/754