# 機能設計書 20-B-Treeストレージエンジン

## 概要

本ドキュメントは、SQLiteにおけるB-Treeストレージエンジン機能について記述する。B-Treeストレージエンジンは、SQLiteのコアストレージレイヤーであり、データベースファイルへの全てのデータアクセスを担当する。

### 本機能の処理概要

**業務上の目的・背景**：データベースシステムにおいて、データの永続化と効率的なアクセスは最も重要な要素である。B-Treeストレージエンジンは、ディスクベースのB-Tree構造を実装し、データの検索・挿入・削除・更新をO(log n)の時間計算量で実行可能にする。テーブルとインデックスの両方を統一的に管理し、ACID特性を保証するための基盤を提供する。

**機能の利用シーン**：
- テーブルへのデータ挿入・更新・削除
- インデックスを使用したデータ検索
- テーブル・インデックスの作成・削除
- トランザクション処理（BEGIN/COMMIT/ROLLBACK）
- カーソル操作によるデータ走査

**主要な処理内容**：
1. データベースファイルのオープン・クローズ
2. B-Treeカーソルの作成・操作
3. データの挿入・削除・検索
4. ページの分割・結合（バランシング）
5. オーバーフローページの管理
6. フリーリストの管理
7. 共有キャッシュとロックの管理

**関連システム・外部連携**：Pager（ページキャッシュ）、VDBE（仮想マシン）

**権限による制御**：読み取りロック、書き込みロック、排他ロック

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 9 | 未定義（speedtest1-f9） | 間接 | パフォーマンステスト |
| 10 | 未定義（speedtest1-f10） | 間接 | パフォーマンステスト |

## 機能種別

ストレージエンジン / B-Tree実装

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| pVfs | sqlite3_vfs* | Yes | VFSインターフェース | - |
| zFilename | const char* | No | データベースファイル名 | NULL可（一時DB） |
| db | sqlite3* | Yes | データベース接続 | 有効な接続 |
| flags | int | Yes | オープンフラグ | BTREE_OMIT_JOURNAL等 |

### 入力データソース

- SQLパーサからのSQL文
- VDBEからのオペコード
- アプリケーションからのAPI呼び出し

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| 戻り値 | int | SQLiteエラーコード |
| ppBtree | Btree** | B-Treeハンドル |
| カーソルデータ | void* | 検索結果データ |

### 出力先

- アプリケーション（クエリ結果）
- データベースファイル（永続化データ）

## 処理フロー

### 処理シーケンス

```
1. データベースオープン（sqlite3BtreeOpen）
   └─ Btree構造体の割り当て
   └─ 共有キャッシュの検索・作成
   └─ Pagerのオープン
   └─ ファイルヘッダーの読み込み・検証

2. トランザクション開始（sqlite3BtreeBeginTrans）
   └─ 読み取り/書き込みトランザクションの取得
   └─ 必要なロックの獲得

3. カーソルオープン（sqlite3BtreeCursor）
   └─ BtCursor構造体の割り当て
   └─ テーブルロックの取得

4. データ操作
   └─ 検索: sqlite3BtreeFirst/Last/Moveto
   └─ 挿入: sqlite3BtreeInsert
   └─ 削除: sqlite3BtreeDelete
   └─ 走査: sqlite3BtreeNext/Previous

5. トランザクション終了
   └─ sqlite3BtreeCommit または sqlite3BtreeRollback

6. データベースクローズ（sqlite3BtreeClose）
   └─ カーソルのクローズ
   └─ Pagerのクローズ
   └─ 共有キャッシュからの削除
```

### フローチャート

```mermaid
flowchart TD
    A[sqlite3BtreeOpen] --> B[Btree構造体作成]
    B --> C{共有キャッシュ?}
    C -->|Yes| D[既存BtSharedを検索]
    C -->|No| E[新規BtShared作成]
    D --> F{見つかった?}
    F -->|Yes| G[参照カウント増加]
    F -->|No| E
    E --> H[Pagerオープン]
    H --> I[ファイルヘッダー読み込み]
    G --> I
    I --> J[初期化完了]

    K[sqlite3BtreeBeginTrans] --> L{書き込み?}
    L -->|Yes| M[WRITE_LOCK取得]
    L -->|No| N[READ_LOCK取得]
    M --> O[トランザクション開始]
    N --> O

    P[sqlite3BtreeInsert] --> Q[カーソル位置決定]
    Q --> R[セル作成]
    R --> S{ページに空きあり?}
    S -->|Yes| T[セル挿入]
    S -->|No| U[ページ分割]
    U --> T
    T --> V[バランシング]

    W[sqlite3BtreeDelete] --> X[セル削除]
    X --> Y{アンダーフロー?}
    Y -->|Yes| Z[ページ結合]
    Y -->|No| AA[完了]
    Z --> AA
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-20-01 | ページサイズ | 512〜65536バイト（2のべき乗） | データベース作成時 |
| BR-20-02 | 最大ツリー深度 | BTCURSOR_MAX_DEPTH=20 | 常時 |
| BR-20-03 | intkey B-Tree | テーブル用、64ビット整数キー | BTREE_INTKEY |
| BR-20-04 | blobkey B-Tree | インデックス用、任意長キー | BTREE_BLOBKEY |
| BR-20-05 | セル最大サイズ | ページサイズ - 8バイト | 常時 |
| BR-20-06 | 最小セル数 | 1ページあたり最低4セル | リーフページ |

### 計算ロジック

**最大セルサイズ**:
```
MX_CELL_SIZE(pBt) = pBt->pageSize - 8
```

**1ページあたり最大セル数**:
```
MX_CELL(pBt) = (pBt->pageSize - 8) / 6
```

## データベース操作仕様

### 操作別データベース影響一覧

| 操作 | 対象 | 操作種別 | 概要 |
|-----|-----|---------|------|
| sqlite3BtreeInsert | B-Tree | 挿入 | セルの追加、必要に応じてページ分割 |
| sqlite3BtreeDelete | B-Tree | 削除 | セルの削除、必要に応じてページ結合 |
| sqlite3BtreeClearTable | テーブル | 削除 | テーブル内全データ削除 |
| sqlite3BtreeDropTable | テーブル | 削除 | テーブル構造自体の削除 |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| SQLITE_CORRUPT | 破損 | データベースファイル破損 | バックアップからリストア |
| SQLITE_FULL | ディスクフル | ディスク容量不足 | ディスク容量確保 |
| SQLITE_IOERR | I/Oエラー | ファイルI/O失敗 | ファイルシステム確認 |
| SQLITE_NOMEM | メモリ不足 | メモリ割り当て失敗 | メモリ確保 |
| SQLITE_LOCKED | ロック競合 | 他接続との競合 | リトライまたは待機 |
| SQLITE_BUSY | ビジー | データベースがビジー | リトライ |

### リトライ仕様

SQLITE_BUSYの場合、busy handlerが設定されていればリトライ。

## トランザクション仕様

### トランザクション状態

| 状態 | 定数 | 説明 |
|-----|------|------|
| TRANS_NONE | 0 | トランザクションなし |
| TRANS_READ | 1 | 読み取りトランザクション |
| TRANS_WRITE | 2 | 書き込みトランザクション |

### ロックの種類

| ロック | 説明 |
|-------|------|
| READ_LOCK | 読み取りロック（共有） |
| WRITE_LOCK | 書き込みロック（排他） |

## パフォーマンス要件

- 検索: O(log n) - ツリー高さに比例
- 挿入: O(log n) - 分割が発生する可能性あり
- 削除: O(log n) - 結合が発生する可能性あり
- シーケンシャルスキャン: O(n)

## セキュリティ考慮事項

- SQLITE_SECURE_DELETE: 削除データのゼロクリア
- 共有キャッシュ時のテーブルロック管理
- ファイルアクセス権限はVFSレイヤーで制御

## 備考

- SQLITE_OMIT_SHARED_CACHE: 共有キャッシュ機能の無効化
- SQLITE_OMIT_AUTOVACUUM: 自動バキューム機能の無効化
- WALモード時はPagerレイヤーで先行書き込みログを管理

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | btreeInt.h | `src/btreeInt.h` | Btree, BtShared, MemPage, BtCursor構造体 |
| 1-2 | btree.h | `src/btree.h` | 公開API定義 |

**読解のコツ**:
- **Btree**: データベース接続ごとのハンドル（345行目）
- **BtShared**: 共有可能なデータベースファイル情報（425行目）
- **MemPage**: メモリ上のページ表現（273行目）
- **BtCursor**: B-Tree走査用カーソル
- **CellInfo**: セル情報（480行目）

#### Step 2: ファイルフォーマットを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | btreeInt.h | `src/btreeInt.h` | 11-215行目のファイルフォーマット説明 |

**主要フォーマット**:
1. **ファイルヘッダー（100バイト）**: ページ1の先頭
   - オフセット0: マジックヘッダー "SQLite format 3"
   - オフセット16-17: ページサイズ
   - オフセット28-31: データベースサイズ（ページ数）
   - オフセット32-35: 最初のフリーリストページ
2. **ページヘッダー（8または12バイト）**: 各B-Treeページ
   - オフセット0: フラグ（intkey, leaf等）
   - オフセット3-4: セル数
   - オフセット8-11: 右子ポインタ（内部ノードのみ）
3. **セルフォーマット**: 可変長
   - 左子ポインタ（内部ノードのみ）
   - ペイロードサイズ
   - キー（intkeyの場合は整数）
   - データ

#### Step 3: 主要APIを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | btree.c | `src/btree.c` | sqlite3BtreeOpen()（2528行目）- データベースオープン |
| 3-2 | btree.c | `src/btree.c` | sqlite3BtreeClose()（2917行目）- データベースクローズ |
| 3-3 | btree.c | `src/btree.c` | sqlite3BtreeInsert()（9394行目）- データ挿入 |
| 3-4 | btree.c | `src/btree.c` | sqlite3BtreeDelete()（9826行目）- データ削除 |

#### Step 4: カーソル操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | btree.c | `src/btree.c` | sqlite3BtreeFirst()（5676行目）- 先頭へ移動 |
| 4-2 | btree.c | `src/btree.c` | sqlite3BtreeLast()（5757行目）- 末尾へ移動 |
| 4-3 | btree.c | `src/btree.c` | sqlite3BtreeNext()（6369行目）- 次へ移動 |
| 4-4 | btree.c | `src/btree.c` | sqlite3BtreePrevious()（6461行目）- 前へ移動 |

### プログラム呼び出し階層図

```
sqlite3BtreeOpen() [btree.c:2528]
    │
    ├─ sqlite3MallocZero() - Btree構造体割り当て
    │
    ├─ (共有キャッシュ検索)
    │      └─ sqlite3SharedCacheList走査
    │
    ├─ sqlite3PagerOpen() [pager.c]
    │      └─ Pager初期化
    │
    └─ ファイルヘッダー読み込み・検証

sqlite3BtreeInsert() [btree.c:9394]
    │
    ├─ saveAllCursors() - 他カーソルの位置保存
    │
    ├─ moveToRoot() / btreeMoveto() - 挿入位置検索
    │
    ├─ btreeOverwriteCell() [上書き時]
    │
    └─ insertCell() / balance() [新規挿入時]
           │
           ├─ allocateBtreePage() - ページ割り当て
           │
           └─ balance_nonroot() / balance_deeper()
                  └─ ページ分割・結合

sqlite3BtreeDelete() [btree.c:9826]
    │
    ├─ saveCursorKey() - カーソルキー保存
    │
    ├─ sqlite3BtreePrevious() [内部ノードの場合]
    │
    ├─ dropCell() - セル削除
    │
    └─ balance() - リバランシング

sqlite3BtreeClose() [btree.c:2917]
    │
    ├─ sqlite3BtreeRollback() - 未コミットトランザクションのロールバック
    │
    ├─ removeFromSharingList() - 共有リストから削除
    │
    └─ sqlite3PagerClose() [pager.c]
           └─ Pager終了処理
```

### データフロー図

```
[入力]                       [処理]                      [出力]

SQL文 ─────────────▶ VDBE OP_*オペコード
                              │
                              ▼
                     sqlite3BtreeCursor()
                              │
                              ▼
                    ┌─────────┴─────────┐
                    ▼                   ▼
              検索操作             更新操作
                    │                   │
                    ▼                   ▼
         sqlite3BtreeMoveto()   sqlite3BtreeInsert()
                    │           sqlite3BtreeDelete()
                    │                   │
                    ▼                   ▼
         B-Treeページ走査       セル操作・バランシング
                    │                   │
                    ▼                   ▼
              MemPage             MemPage（変更）
                    │                   │
                    ▼                   ▼
             Pager読み取り        Pager書き込み
                    │                   │
                    └─────────┬─────────┘
                              ▼
                        データベースファイル
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| btree.c | `src/btree.c` | ソース | B-Treeメイン実装 |
| btreeInt.h | `src/btreeInt.h` | ヘッダー | 内部構造体・フォーマット定義 |
| btree.h | `src/btree.h` | ヘッダー | 公開API定義 |
| btmutex.c | `src/btmutex.c` | ソース | B-Tree用ミューテックス |
| pager.c | `src/pager.c` | ソース | ページキャッシュ管理 |
| pager.h | `src/pager.h` | ヘッダー | Pager API定義 |
