# 機能設計書 37-R-Tree空間インデックス

## 概要

本ドキュメントは、SQLiteにおけるR-Tree空間インデックス機能の設計仕様を定義する。多次元空間データ（地理座標、矩形領域等）に対する高速な範囲検索を実現する仮想テーブルモジュールである。

### 本機能の処理概要

R-Treeは、Antonin Guttmanが1984年に提案した空間データ構造で、多次元データの効率的な検索を可能にする。SQLiteのR-Tree実装は、1〜5次元のデータをサポートし、R*-treeアルゴリズムを使用する。

**業務上の目的・背景**：地理情報システム（GIS）、CAD、ゲーム等のアプリケーションでは、空間データ（点、線、多角形）の効率的な検索が必要である。通常のB-Treeインデックスは1次元データに最適化されているが、R-Treeは多次元データに対して最適化されている。

**機能の利用シーン**：
- 地図アプリケーションでの「この範囲内のPOI（Point of Interest）を検索」
- ゲームでの衝突検出（オブジェクト同士の重なり判定）
- CADでの「この領域に含まれる図形を選択」
- 不動産検索での「この地域内の物件を検索」

**主要な処理内容**：
1. CREATE VIRTUAL TABLE...USING rtreeでR-Treeテーブルを作成
2. 各次元の最小値・最大値を指定してデータを挿入
3. 範囲検索（<=, >=, BETWEEN）またはMATCH演算子で空間クエリを実行
4. カスタムジオメトリコールバックでより複雑な空間クエリをサポート
5. Geopoly拡張で多角形データをサポート

**関連システム・外部連携**：
- 仮想テーブルモジュール：R-Treeは仮想テーブルとして実装
- シャドウテーブル：_node, _rowid, _parent
- Geopoly拡張：R-Tree上に構築された多角形サポート

**権限による制御**：
- 通常のテーブル同様、sqlite3_set_authorizer()による認可チェック

## 関連画面

本機能はSQLite内部機能のため、直接的な画面関連はない。

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 8 | SQLite3 Fiddle | 参照画面 | R-Treeテーブルの作成・検索 |

## 機能種別

空間インデックス / 範囲検索 / 仮想テーブル

## 入力仕様

### 入力パラメータ（テーブル作成）

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| table_name | TEXT | Yes | R-Treeテーブル名 | 有効な識別子 |
| id | INTEGER | Yes | 主キー（64ビット整数） | 正の整数 |
| minX, maxX | REAL/INT | Yes | X軸の最小値・最大値 | minX <= maxX |
| minY, maxY | REAL/INT | No | Y軸の最小値・最大値（2次元以上） | minY <= maxY |
| ... | ... | No | 最大5次元までサポート | - |
| +aux_column | ANY | No | 補助カラム（R-Tree 3.24.0+） | - |

### 座標型

| オプション | 座標型 | 説明 |
|-----------|--------|------|
| rtree | 32ビット浮動小数点 | デフォルト |
| rtree_i32 | 32ビット整数 | 整数座標が必要な場合 |

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| id | INTEGER | 行識別子 |
| minX, maxX | REAL/INT | 各次元の境界 |
| 補助カラム | ANY | +で定義したカラム |

### 出力先

- 結果セット（SELECT文の結果）
- カスタムジオメトリコールバックの結果

## 処理フロー

### 処理シーケンス

```
1. テーブル作成フェーズ
   ├─ CREATE VIRTUAL TABLE...USING rtree
   ├─ シャドウテーブル作成（_node, _rowid, _parent）
   └─ ルートノード（nodeno=1）の初期化

2. データ挿入フェーズ
   ├─ 適切なリーフノードを検索
   ├─ セルを挿入
   ├─ ノードがオーバーフローした場合、分割
   └─ 必要に応じて再挿入（R*-tree）

3. 範囲検索フェーズ
   ├─ ルートノードから検索開始
   ├─ 各ノードでバウンディングボックスをチェック
   ├─ 重複するノードを再帰的に探索
   └─ リーフノードから結果を収集

4. カスタムジオメトリクエリフェーズ
   ├─ MATCH演算子でジオメトリ関数を指定
   ├─ 各候補セルに対してコールバックを呼び出し
   └─ FULLY_WITHIN/PARTLY_WITHIN/NOT_WITHINを返却
```

### フローチャート

```mermaid
flowchart TD
    A[INSERT INTO rtree_table] --> B[ChooseLeaf: 適切なリーフ検索]
    B --> C[セル挿入]
    C --> D{ノードオーバーフロー?}
    D -->|Yes| E[SplitNode: ノード分割]
    D -->|No| F[完了]
    E --> G[AdjustTree: 親ノード更新]
    G --> D

    H[SELECT WHERE minX <= ? AND maxX >= ?] --> I[ルートノードから検索]
    I --> J[バウンディングボックスチェック]
    J --> K{重複あり?}
    K -->|Yes| L{リーフノード?}
    K -->|No| M[次のエントリ]
    L -->|Yes| N[結果に追加]
    L -->|No| O[子ノードを再帰探索]
    O --> J
    N --> M
    M --> P{全エントリ処理完了?}
    P -->|No| J
    P -->|Yes| Q[結果返却]
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-37-1 | 境界条件 | 各次元でmin <= maxでなければならない | INSERT/UPDATE時 |
| BR-37-2 | 次元固定 | テーブル作成後、次元数は変更不可 | 常時 |
| BR-37-3 | ID制約 | idは64ビット正整数で一意 | INSERT時 |
| BR-37-4 | ノードサイズ | ノードサイズはページサイズ以下 | 常時 |
| BR-37-5 | 最小セル数 | ノードには最小M/3個のセルが必要 | 削除時 |

### 計算ロジック

**ノードサイズ計算**：
- デフォルト: 64バイトのセル
- セルサイズ: 8バイト(rowid) + nDim * 2 * 4バイト(座標)
- 最大セル数: (nodeSize - 4) / cellSize

**R*-tree最小セル数**：
- m = M/3（Guttmanの論文に基づく）

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

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

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| CREATE | rtree_table | CREATE | 仮想テーブル作成 |
| CREATE | rtree_table_node | CREATE | ノードデータ格納 |
| CREATE | rtree_table_rowid | CREATE | rowid→ノードマッピング |
| CREATE | rtree_table_parent | CREATE | 親ノード関係 |
| INSERT | 全シャドウテーブル | INSERT | 空間データ追加 |

### テーブル別操作詳細

#### _node

| 操作 | 項目（カラム名） | 更新値・取得条件 | 備考 |
|-----|-----------------|-----------------|------|
| INSERT/UPDATE | nodeno | 自動採番 | ノード番号 |
| INSERT/UPDATE | data | BLOB | ノードデータ（セル配列） |

#### _rowid

| 操作 | 項目（カラム名） | 更新値・取得条件 | 備考 |
|-----|-----------------|-----------------|------|
| INSERT | rowid | ユーザー指定 | 行ID |
| INSERT | nodeno | 所属ノード | リーフノード番号 |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| SQLITE_CONSTRAINT | 制約違反 | minX > maxX等 | 境界値を修正 |
| SQLITE_CONSTRAINT | 一意制約 | 重複するid | 一意のidを使用 |
| SQLITE_CORRUPT | データ破損 | シャドウテーブル破損 | テーブル再作成 |
| SQLITE_ERROR | 次元エラー | 次元数不一致 | 正しい次元数を指定 |

### リトライ仕様

R-Tree操作のエラーは基本的にリトライ不可。データ破損時はテーブルの再作成が必要。

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

- R-Tree操作は通常のトランザクション内で実行可能
- ロールバック時、シャドウテーブルの変更も取り消される
- WALモードでの並行読み取りをサポート

## パフォーマンス要件

- 検索計算量: O(log n)（バランスの取れた木）
- 挿入計算量: O(log n)
- R*-treeアルゴリズムにより、ノードの重複を最小化
- RTREE_DEFAULT_ROWEST（1048576）を初期推定行数として使用

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

- シャドウテーブルへの直接アクセスは推奨されない
- カスタムジオメトリコールバックはC言語で実装されるため、メモリ安全性に注意

## 備考

- SQLITE_ENABLE_RTREEでコンパイル時に有効化
- 最大5次元（RTREE_MAX_DIMENSIONS）をサポート
- 補助カラム（+aux）はR-Tree 3.24.0以降でサポート
- Geopoly拡張は多角形データをサポート（SQLITE_ENABLE_GEOPOLY）

---

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

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

### 推奨読解順序

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

R-Treeの中核となるデータ構造を理解する。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | rtree.c | `ext/rtree/rtree.c` | 16-54行目のデータベースフォーマットコメント |
| 1-2 | rtree.c | `ext/rtree/rtree.c` | 160-214行目のRtree構造体 |
| 1-3 | rtree.c | `ext/rtree/rtree.c` | 253-259行目のRtreeSearchPoint構造体 |

**読解のコツ**: _node、_parent、_rowidの3つのシャドウテーブルの役割を理解する。ノードデータは先頭2バイトが深さ（ルートのみ）、次の2バイトがエントリ数。

#### Step 2: ノード構造を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | rtree.c | `ext/rtree/rtree.c` | 40-54行目のノードフォーマットコメント |

**主要処理フロー**:
- ルートノード: 先頭2バイトが木の深さ
- 非ルートノード: 先頭2バイトは未使用
- エントリ: 8バイトrowid + nDim*2*4バイト座標

#### Step 3: 検索処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | rtree.c | `ext/rtree/rtree.c` | rtreeFilter()、rtreeNext()関数 |

**主要処理フロー**:
- 優先度キューを使用した検索
- バウンディングボックスの重複チェック
- リーフノードからの結果収集

#### Step 4: 挿入処理を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | rtree.c | `ext/rtree/rtree.c` | rtreeInsertCell()関数 |

**主要処理フロー**:
- ChooseLeaf: 適切なリーフノードの選択
- ノード分割（R*-tree）
- AdjustTree: 親ノードの更新

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

```
CREATE VIRTUAL TABLE...USING rtree
    │
    └─ rtreeInit()
           │
           ├─ シャドウテーブル作成
           └─ ルートノード初期化（nodeno=1）

INSERT INTO rtree_table
    │
    └─ rtreeUpdate()
           │
           └─ rtreeInsertCell()
                  │
                  ├─ ChooseLeaf()  適切なリーフ選択
                  ├─ nodeInsertCell()  セル挿入
                  └─ SplitNode()  必要に応じて分割

SELECT WHERE minX <= ? AND maxX >= ?
    │
    ├─ rtreeBestIndex()  クエリプラン
    │
    └─ rtreeFilter()
           │
           ├─ 制約からバウンディングボックス計算
           │
           └─ rtreeNext()  優先度キューで検索
                  │
                  └─ rtreeStepToLeaf()  リーフまで探索

MATCH rtreegeom(...)
    │
    └─ カスタムジオメトリコールバック
           │
           └─ FULLY_WITHIN/PARTLY_WITHIN/NOT_WITHIN
```

### データフロー図

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

id, minX, maxX, ... ───────▶ rtreeInsertCell() ────────────▶ _node, _rowid
空間データ                   R-Tree挿入                      シャドウテーブル

WHERE minX <= ? ... ───────▶ rtreeFilter() ────────────────▶ 結果セット
範囲条件                     バウンディングボックス検索       マッチする行

MATCH rtreegeom() ─────────▶ カスタムコールバック ──────────▶ フィルタ結果
ジオメトリ関数               xGeom()                         WITHIN判定

_node ─────────────────────▶ nodeAcquire() ────────────────▶ RtreeNode
シャドウテーブル             ノードキャッシュ                 メモリ上のノード
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| rtree.c | `ext/rtree/rtree.c` | ソース | R-Treeメイン実装 |
| sqlite3rtree.h | `ext/rtree/sqlite3rtree.h` | ヘッダー | 公開API定義 |
| geopoly.c | `ext/rtree/geopoly.c` | ソース | Geopoly拡張（多角形サポート） |
| test_rtreedoc.c | `ext/rtree/test_rtreedoc.c` | ソース | テスト用実装 |
