🌲

Rustでデータ構造書いてみた(B木編)

2025/01/21に公開

はじめに

この記事は jack Advent Calendar 2024 の記事の再掲です.

概要

B 木とは

B 木は,データを常にソートされた状態で管理することができるデータ構造の 1 種です.

また,赤黒木のように,データの挿入や削除で木のバランスが崩れることがないように自動的にバランスを保つ機能を持っています.(このような性質をもつ木構造を「平衡木」と呼びます.)

一方で,有名な平衡木の多くは分岐が 2 つまでしかない2 分木ですが,B 木は分岐数をいくらでも増やすことができるという特徴を持っています.

B 木のメリット / 実用例

平衡 2 分木と比較した際,B 木は分岐数が多いため,同じデータ数の場合では木の高さを低く抑えることができます.そのため,ノード間の移動のコストが大きい場合には 2 分木よりも高速に動作するようになります.

  • ハードディスク上のデータ保管
    ハードディスクはその構造からシーケンシャルアクセスは高速,ランダムアクセスは低速という特性をもつため,ランダムアクセスの多い 2 分木は低速になってしまいます.一方,B 木は 1 つのノードが持つデータ数が多いため,ランダムアクセスの回数を減らすことができ,高速に動作させられます.
  • 多くのリレーショナルデータベース(RDB)の内部実装
    ハードディスクに置くことが多いからみたいです.
  • Rust のソート済み集合
    Rust ではキャッシュ効率の観点からソート済み集合に B 木を採用しています [1]

B 木の仕組み

では,実際に B 木の中身がどうなっているのかを見ていきましょう!

B 木の定義

B 木には定義があり,この定義を満たすように挿入や削除を行うことで木の平衡を保つことができます.(よくわからない場合は飛ばして読み進めても大丈夫です)

B 木の定義

B 木 T は,以下の性質をもつ根付き木です.(定義はアルゴリズムイントロダクション[1]に準拠しましたが,多少端折っている部分もあるので詳細はそちらを参照してください)

  1. 各ノード x は以下の属性を持つ

    1. x に格納されているキーの数 x.n (単に xサイズともいう)
    2. 格納されている x.n 個のキー x.\mathit{key}_1, x.\mathit{key}_2, \ldots, x.\mathit{key}_n は昇順に並べられている
    3. x が葉であればTrue,内部ノードであればFalseとなるブール値 x.\mathit{leaf}
  2. ノード x が内部ノードであれば,x.n+1 個のポインタ x.c_1, x.c_2, \ldots, x.c_{n+1} を持つ

  3. 各ノードについて,キー x.\mathit{key}_ix.\mathit{key}_{i+1} の間にある子 x.c_i が持つ値 k_i

    x.\mathit{key}_i \le k_i \le x.\mathit{key}_{i+1}

    となる.(両端の子についても同様)

  4. すべての葉は同じ深さを持つ

  5. 1 つのノードが格納できるキーの数には上限と下限が存在する.これは B 木の最小次数と呼ばれる値 t~(t\ge 2) を用いて表される.(最小次数は B 木 T に固有の定数である)

    1. 根を除くすべてのノードは少なくとも t-1 個のキーをもつ.したがって,根を除くすべての内部ノードは少なくとも t 個の子をもつ.木が空でなければ根は少なくとも 1 個のキーをもつ.
    2. どのノードも最大 2t-1 個のキーを持つことができる.したがって,内部ノードは最大 2t 個の子を持つことができる.ちょうど 2t-1 個キーをもつ内部接点は飽和しているという.

最小次数が t=2 のとき,各ノードのキーは t-1=1 個以上 2t-1 = 3 個以下であり,下の図のようになります.

B木-t=2.png

最小次数が t=3 のとき,根以外の各ノードのキーは t-1 = 2 個以上 2t-1 = 5 個以下であり,下図のようになります.

B木-template.png

以下,上の t=3 の木を用いて解説してきます.

検索

B 木 T に値 k を持つキーが存在するか調べる場合を考えます.以下のようなアルゴリズムで実現できます.

アルゴリズム: \text{B-Tree-Find}(T, k)

  1. xT の根へのポインタで初期化する.
  2. x が葉でない間以下を繰り返す.
    1. x の各キーについて順に,
      1. k がキーより小さければ x をキーの左の子に更新して 2 に戻る.
      2. k がキーに一致すればTrueを返す.
    2. kx のどのキーよりも大きければ xx の最も右の子に更新する.
  3. x が葉である場合,xk と等しいキーがあればTrue,そうでなければFalseを返す.

29 を検索する場合は以下のようになります.

  1. 20 < 29 なので右の子に移動します.

B木-find1.png

  1. 25 < 29 < 33 なので 33 の左の子に移動します.

B木-find2.png

  1. 29 のノードが見つかったのでTrueを返します.

B木-find3.png

挿入

次に挿入について考えます.B 木への挿入は,検索と同様に適切なノードをたどりながら行いますが,飽和したノードに挿入されないよう,ノードの分割を行いつつたどっていきます.

B 木 T にキー k を挿入するアルゴリズムは以下のとおりです.

アルゴリズム: \text{B-Tree-Insert}(T, k)

  1. xT の根へのポインタで初期化する.
  2. x が葉でない間以下を繰り返す.
    1. x が飽和していれば,ノードの分割を行う.
    2. x の各キーについて順に,
      1. k がキーより小さければ x をキーの左の子に更新して 2 に戻る.
    3. kx のどのキーよりも大きければ xx の最も右の子に更新する.
  3. 葉への挿入でキー k を挿入する.

ノードの分割,葉への挿入については以下のとおりです.

ノードの分割

2t-1 個のキーをもつノードを

  • 小さい方から t-1
  • 中央値 1
  • 大きい方から t-1

に分割します.小さい方から t-1 個,大きい方から t-1 個をそれぞれ別のノードに移し,中央値を親に移動します.

B木-split.png

葉への挿入(サイズが 2t-2 以下のとき)

ノードが葉であり, 2t-2 個以下のキーしか持っていない場合はソート済み配列への挿入と同じようにすればよいです.

B木-insert(leaf).png

葉への挿入(サイズが 2t-1 個のとき)

ノードが葉であり,ちょうど 2t-1 個のキーを持っている場合には,直接挿入することができません.(キーの数が 2t 個になって B 木の条件を満たさなくなってしまうため)

そこで,ノードを分割してから挿入します.

B木-insert(split).png

28 を挿入する場合は以下のようになります.

  1. 右の子に進みます.

B木-insert1.png

  1. 33 の左の子に進みます.

B木-insert2.png

  1. すでに 5 個のキーを持っているので,ノードを分割します.

    その後,30 の左の子に進みます.

B木-insert3.png

  1. 27,29 の間に挿入します.

B木-insert4.png

→ これで挿入ができました!

削除

B 木 T からキー k を削除するアルゴリズムは以下のとおりです.(ノード kT に存在することを仮定します)

アルゴリズム: \text{B-Tree-Remove}(T, k)

xT の根へのポインタで初期化する.
その後,以下の場合分けにしたがう.

  1. キー k がノード x に存在し,x が葉であるとき,kx から削除する
  2. キー k がノード x に存在し,x が内部ノードであるとき,
    1. x における k の直前の子 y のサイズが t 以上のとき
      y の部分木の最大値 k' を削除し,x において kk' に置き換える
    2. x における k の直後の子 z のサイズが t 以上のとき
      z の部分木の最小値 k' を削除し,x において kk' に置き換える
    3. yz のサイズがいずれも t-1 のとき
      y,k,z をこの順で併合し,併合したノードから k を削除する
  3. キー k がノード x に存在しないとき,キー k を部分木に含むような x の子 x.c_i を特定する.x.c_i のサイズが t-1 のとき,ステップ 3-1, 3-2 のいずれかを実行し,x の適切な子に再帰する.
    1. x.c_i のサイズが t-1 であり,かつ,x.c_{i-1} または x.c_{i+1} のサイズが t のとき
      x のキーを x.c_i に移す.その代わりとして,x.c_{i-1} の最大値,または x.c_{i+1} の最小値を削除し,元あった場所に挿入する.x.c_{i-1} または x.c_{i+1} の適切な子ポインタも x.c_i に移動する.
    2. x.c_i のサイズが t-1 であり,かつ,x.c_{i-1}x.c_{i+1} のサイズがどちらも t-1 のとき
      x.c_i をどちらかの兄弟と併合する

また,ノードの併合は次のように行います.

ノードの併合

ノード x のキー x.\mathit{key}_i の左の子 x.c_i ,右の子 x.c_{i+1} のサイズがともに t-1 であるとき,
kx.c_{i+1} のキーをこの順に x.c_i に移し,x.c_{i+1} を削除します.z.c_{i+1} 子のポインタについても適切に移動します.

B木-merge.png

では,B 木からの削除について実際にみていきましょう.

1. 葉からの削除

27 を削除する場合を考えます.

  1. 20 の右の子に進みます

remove1_1.png

  1. 30 の左の子に進みます.

B木の削除-remove1_2.png

  1. 27 を発見したので削除します.

B木の削除-remove1_3.png

  1. これで完了です.

B木の削除-remove1_4.png

2-1. 内部ノードからの削除(左右のいずれかの子のサイズが t 以上)

15 を削除する場合を考えます.

  1. 20 の左の子に進みます.

B木の削除-remove2_a_1.png

  1. 15 を発見しますが,そのまま消すことはできません.
    15 の左の子のサイズが t ~(=3) 以上なので 15 の左の子から最大値 12 を削除します.

B木の削除-remove2_a_2.png

  1. 15 を削除し,その位置を先ほど取ってきた 12 を入れて完了です.

B木の削除-remove2_a_3.png

2-2. 内部ノードからの削除(左右の両方の子のサイズが t-1 以下)

30 を削除する場合を考えます.

  1. 20 の右の子に進みます.

B木の削除-remove2_b_1.png

  1. 30 を発見しますが,そのまま消すことはできません.
    30 の左の子と右の子のサイズがともに t-1~(=2) なので,それらをマージします.

B木の削除-remove2_b_2.png

  1. マージされた頂点に進みます.

B木の削除-remove2_b_3.png

  1. マージされた頂点から値を削除します.

B木の削除-remove2_b_4.png

  1. これで完了です.

B木の削除-remove2_b_5.png

3-1/3-2. サイズが t-1 以下のノードに進む場合

22 を削除する場合を考えます.

  1. 根ノードの 2 つの子のサイズがともに t-1~(=2) なので,これらをマージします.(3-2)

B木の削除-remove3_b_1.png

  1. マージが完了しました.

B木の削除-remove3_b_2.png

  1. 25 の左の子に進みますが,このノードのサイズは t-1 しかないのでそのままでは進めません.

B木の削除-remove3_a_1.png

  1. 25 の右の子のサイズは t~(=3) 以上なので,ここから最小値を削除します.

B木の削除-remove3_a_2.png

  1. 削除した最小値を左の子に移します.これで左の子のサイズが t 以上になりました!
    27 の左の子に移動します.

B木の削除-remove3_a_2_2.png

  1. 22 を削除します.

B木の削除-remove3_a_3.png

  1. これで完了です!

remove3_a_4.png

まとめ

ここまで,

  • B 木上の検索
  • B 木への挿入
  • B 木からの削除

について説明しました.

また,実装はこちらにアップロードしました:kentakom1213/rust-btree
各操作については,

をご覧ください.
動かして遊べるページも作ったのでぜひ試してみてください:B 木 - Rust Playground

参考文献

  1. 浅野哲夫.「アルゴリズムイントロダクション」第 3 版 第 2 巻,近代科学社,2012 年,p106-121
  2. B 木,Wikipedia,https://ja.wikipedia.org/wiki/B 木,2024 年 12 月 3 日閲覧
脚注
  1. https://doc.rust-lang.org/std/collections/btree_map/struct.BTreeMap.html ↩︎

Discussion