5
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 13

デジタル創作サークルUniProject Advent Calendar 2025

Day 24

あくあ Advent Calendar 2025

@Aqua-218(Aqua)inデジタル創作サークルUniProject

【Rust】データベースを自作する Part1 - B-Treeって何？データ構造から理解する

Posted at

シリーズ一覧

Part タイトル 内容
1 B-Treeって何？データ構造から理解する ← 今ここ
2 ページ管理とバッファプール ディスクI/Oの抽象化
3 SQLパーサーを書く SQL文を解析する
4 クエリ実行エンジン 実行計画と処理
5 トランザクションとWAL ACID特性の実装
6 インデックスとクエリ最適化 高速化の仕組み

はじめに

データベースって中で何やってるか知ってる？

「INSERT したら保存されて、SELECT したら取れる」

...まあそうなんだけど、どうやって高速に検索してるの？

答えは B-Tree（ビーツリー）というデータ構造。

MySQLもPostgreSQLもSQLiteも、みんなB-Treeを使ってる。

今回はRustでB-Treeを実装しながら、データベースの心臓部を理解していこう。

B-Treeとは

なぜ二分木じゃダメなの？

まず「なぜB-Tree？」という話から。

普通の二分探索木（BST）でもO(log n)で検索できる。でもデータベースには向いてない。

理由はディスクI/O。

二分木の場合：
     50
    /  \
   25   75      ← 各ノードが1つのキーしか持たない
  / \   / \         → 深さが深くなる
 10 30 60 90        → ディスクアクセスが増える

ディスクからデータを読むのはめちゃくちゃ遅い（メモリの10万倍以上）。

だから「1回のディスクアクセスでなるべく多くの情報を取りたい」。

B-Treeの特徴

B-Tree（次数3）の場合：

        [30, 60]              ← 1ノードに複数キー
       /    |    \
  [10,20] [40,50] [70,80,90]  ← 深さが浅い = ディスクアクセス少ない

B-Treeの特徴：

  1. 1ノードに複数のキーを持てる
  2. すべてのリーフが同じ深さ（バランス保証）
  3. ノードは常に半分以上埋まる（効率保証）

B-Treeのルール

次数 t（最小次数）のB-Treeには以下のルールがある：

ルール 説明
最大キー数 2t - 1
最小キー数 t - 1（ルート除く）
最大子ノード数 2t
最小子ノード数 t（ルート除く）

例えば t = 2 なら：

  • 各ノードは最大3キー
  • 各ノードは最低1キー（ルート除く）
  • 各ノードは最大4つの子

Rustで実装してみる

ノードの定義

/// B-Treeのノード
#[derive(Debug, Clone)]
pub struct BTreeNode<K: Ord + Clone, V: Clone> {
    /// キーの配列
    pub keys: Vec<K>,
    /// 値の配列（キーと1対1対応）
    pub values: Vec<V>,
    /// 子ノードのインデックス（リーフの場合は空）
    pub children: Vec<usize>,
    /// リーフノードかどうか
    pub is_leaf: bool,
}

ポイント：

  • keysとvaluesは1対1：key[i]に対応する値がvalue[i]
  • childrenはkeysより1つ多い：n個のキーがあれば、n+1個の子がある
  • is_leaf：リーフノードかどうか

ノードの構造（図解）

内部ノード（is_leaf = false）:

  children[0]  keys[0]  children[1]  keys[1]  children[2]
      ↓          ↓          ↓          ↓          ↓
     [A]        20        [B]        40        [C]
      
  A: 20未満のキー
  B: 20以上40未満のキー
  C: 40以上のキー


リーフノード（is_leaf = true）:

  keys:   [10, 20, 30]
  values: ["a", "b", "c"]
  children: []  (空)

キーの検索

ノード内でのキー検索は二分探索を使う。

impl<K: Ord + Clone, V: Clone> BTreeNode<K, V> {
    /// ノード内でキーを検索
    /// 見つかった場合は Ok(index)、見つからなかった場合は Err(insert_position)
    pub fn search_key(&self, key: &K) -> Result<usize, usize> {
        self.keys.binary_search(key)
    }
}

Rustのbinary_searchは：

  • 見つかったら Ok(index)
  • 見つからなかったら Err(挿入すべき位置) を返す

この「挿入すべき位置」がどの子ノードに進むべきかを教えてくれる。

B-Tree本体

/// B-Tree本体
#[derive(Debug)]
pub struct BTree<K: Ord + Clone + Debug, V: Clone + Debug> {
    /// ノードの配列（インデックスでアクセス）
    nodes: Vec<BTreeNode<K, V>>,
    /// ルートノードのインデックス
    root: Option<usize>,
    /// 最小次数
    t: usize,
}

ここではノードをVecで管理してインデックスで参照している。

実際のデータベースでは「ページ番号」に相当する部分。

検索の実装

impl<K: Ord + Clone + Debug, V: Clone + Debug> BTree<K, V> {
    /// キーを検索
    pub fn search(&self, key: &K) -> Option<&V> {
        let root_idx = self.root?;
        self.search_node(root_idx, key)
    }

    /// ノード内を再帰的に検索
    fn search_node(&self, node_idx: usize, key: &K) -> Option<&V> {
        let node = &self.nodes[node_idx];
        
        match node.search_key(key) {
            Ok(idx) => {
                // キーが見つかった
                Some(&node.values[idx])
            }
            Err(idx) => {
                // キーが見つからなかった
                if node.is_leaf {
                    // リーフなら存在しない
                    None
                } else {
                    // 子ノードを探索
                    let child_idx = node.children[idx];
                    self.search_node(child_idx, key)
                }
            }
        }
    }
}

検索の流れ：

  1. ルートから始める
  2. ノード内でキーを二分探索
  3. 見つかれば値を返す
  4. 見つからなければ適切な子ノードに再帰

計算量は O(log n)。しかもディスクアクセスは木の高さ分だけ。

挿入の実装

挿入が複雑なのはノードの分割があるから。

/// キーと値を挿入
pub fn insert(&mut self, key: K, value: V) {
    match self.root {
        None => {
            // 空のツリー：新しいルートを作成
            let mut root_node = BTreeNode::new_leaf();
            root_node.keys.push(key);
            root_node.values.push(value);
            let root_idx = self.allocate_node(root_node);
            self.root = Some(root_idx);
        }
        Some(root_idx) => {
            if self.nodes[root_idx].is_full(self.max_keys()) {
                // ルートが満杯：新しいルートを作成して分割
                let old_root_idx = root_idx;
                let mut new_root = BTreeNode::new_internal();
                new_root.children.push(old_root_idx);
                let new_root_idx = self.allocate_node(new_root);
                self.root = Some(new_root_idx);
                
                // 古いルートを分割
                self.split_child(new_root_idx, 0);
                
                // 新しいルートから挿入
                self.insert_non_full(new_root_idx, key, value);
            } else {
                self.insert_non_full(root_idx, key, value);
            }
        }
    }
}

ノードの分割

B-Treeの肝は「事前分割」。

満杯のノードに出会ったら、挿入前に分割する。

/// 子ノードを分割
fn split_child(&mut self, parent_idx: usize, child_idx_in_parent: usize) {
    let t = self.t;
    let child_idx = self.nodes[parent_idx].children[child_idx_in_parent];
    
    // 中央のキーを取得
    let mid = t - 1;
    let mid_key = self.nodes[child_idx].keys[mid].clone();
    let mid_value = self.nodes[child_idx].values[mid].clone();
    
    // 右半分を新しいノードに移動
    let mut new_node = BTreeNode::new_leaf();  // or new_internal()
    new_node.keys = self.nodes[child_idx].keys.split_off(mid + 1);
    new_node.values = self.nodes[child_idx].values.split_off(mid + 1);
    
    // 中央のキーを親に昇格
    // ...
}

分割の様子：

分割前（次数t=2、最大3キー）:
  親: [50]
       ↓
  子: [10, 20, 30]  ← 満杯！ここに40を入れたい

分割後:
  親: [20, 50]      ← 中央の20が昇格
      /      \
  [10]      [30]    ← 左右に分割

この状態なら40を[30]のノードに入れられる

動作確認

実際に動かしてみよう。

fn main() {
    // 次数2のB-Tree（各ノード最大3キー）
    let mut tree = BTree::new(2);

    println!("--- 挿入: 10, 20, 30 ---");
    tree.insert(10, "ten");
    tree.insert(20, "twenty");
    tree.insert(30, "thirty");
    tree.debug_print();

    println!("\n--- 挿入: 40 (ルート分割が発生) ---");
    tree.insert(40, "forty");
    tree.debug_print();
}

実行結果：

--- 挿入: 10, 20, 30 ---
B-Tree (t=2)
[0] Leaf keys=[10, 20, 30]

--- 挿入: 40 (ルート分割が発生) ---
B-Tree (t=2)
[1] Internal keys=[20]
  [0] Leaf keys=[10]
  [2] Leaf keys=[30, 40]

最初は1つのノードに[10, 20, 30]が入ってる。

40を挿入しようとすると満杯なので、20が昇格して新しいルートになる。

もう少し挿入してみる：

--- 挿入: 50, 25, 5 ---
B-Tree (t=2)
[1] Internal keys=[20, 40]
  [0] Leaf keys=[5, 10]
  [2] Leaf keys=[25, 30]
  [3] Leaf keys=[50]

ちゃんとバランスが保たれてる！

大量データの挿入

let mut big_tree = BTree::new(4); // 次数4（各ノード最大7キー）

for i in (0..50).rev() {
    big_tree.insert(i, format!("item_{}", i));
}

big_tree.debug_print();

結果：

B-Tree (t=4)
[9] Internal keys=[18, 34]
  [1] Internal keys=[6, 10, 14]
    [0] Leaf keys=[0, 1, 2, 3, 4, 5]
    [14] Leaf keys=[7, 8, 9]
    [13] Leaf keys=[11, 12, 13]
    [12] Leaf keys=[15, 16, 17]
  [15] Internal keys=[22, 26, 30]
    [11] Leaf keys=[19, 20, 21]
    [8] Leaf keys=[23, 24, 25]
    [7] Leaf keys=[27, 28, 29]
    [6] Leaf keys=[31, 32, 33]
  [10] Internal keys=[38, 42, 46]
    [5] Leaf keys=[35, 36, 37]
    [4] Leaf keys=[39, 40, 41]
    [3] Leaf keys=[43, 44, 45]
    [2] Leaf keys=[47, 48, 49]

50件のデータが、深さ3の木に収まってる。

検索は最大3回のノードアクセスで完了する。

B-Treeの計算量

操作 計算量
検索 O(log n)
挿入 O(log n)
削除 O(log n)

すべてO(log n)。しかもディスクI/Oの観点でも効率的。

なぜデータベースにB-Treeが使われるか

  1. ディスクI/O効率：1ノードを1ページ（通常4KB〜16KB）にマッピング
  2. 範囲検索が高速：キーがソートされてるので、範囲クエリが得意
  3. 常にバランス：最悪ケースでもO(log n)を保証
  4. キャッシュ効率：頻繁にアクセスされるノード（ルート付近）をメモリに保持

B-Treeの亜種

実際のデータベースでは派生形が使われることも多い。

種類 特徴
B+Tree データはリーフのみ、内部ノードはキーのみ
B*Tree 兄弟ノード間で再分配、空間効率UP

特にB+Treeは：

  • リーフ同士がリンクで繋がってる
  • 範囲検索がさらに高速
  • MySQLのInnoDBはB+Treeを使ってる

まとめ

今回作ったもの：

  • B-Treeのノード構造
  • 検索（再帰的な二分探索）
  • 挿入（事前分割方式）

B-Treeはデータベースの心臓部。

この仕組みを理解すると、なぜインデックスを貼ると速くなるのか、なぜ複合インデックスの順番が大事なのか、全部わかってくる。

次回はこのB-Treeをディスク上で永続化する仕組み（ページ管理とバッファプール）を実装していくよ。

この記事が役に立ったら、いいね・ストックしてもらえると嬉しいです！

5
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?