Rustでデータ構造書いてみた(B木編)
はじめに
この記事は jack Advent Calendar 2024 の記事の再掲です.
概要
- B 木の操作について説明したよ
- 検索
- 挿入
- 削除
- Rust で B 木の実装をしたよ
- ソースコード:kentakom1213/rust-btree
- ここから動かせるよ:B 木 - Rust-Playground
B 木とは
B 木は,データを常にソートされた状態で管理することができるデータ構造の 1 種です.
また,赤黒木のように,データの挿入や削除で木のバランスが崩れることがないように自動的にバランスを保つ機能を持っています.(このような性質をもつ木構造を「平衡木」と呼びます.)
一方で,有名な平衡木の多くは分岐が 2 つまでしかない2 分木ですが,B 木は分岐数をいくらでも増やすことができるという特徴を持っています.
B 木のメリット / 実用例
平衡 2 分木と比較した際,B 木は分岐数が多いため,同じデータ数の場合では木の高さを低く抑えることができます.そのため,ノード間の移動のコストが大きい場合には 2 分木よりも高速に動作するようになります.
- ハードディスク上のデータ保管
ハードディスクはその構造からシーケンシャルアクセスは高速,ランダムアクセスは低速という特性をもつため,ランダムアクセスの多い 2 分木は低速になってしまいます.一方,B 木は 1 つのノードが持つデータ数が多いため,ランダムアクセスの回数を減らすことができ,高速に動作させられます. - 多くのリレーショナルデータベース(RDB)の内部実装
ハードディスクに置くことが多いからみたいです. - Rust のソート済み集合
Rust ではキャッシュ効率の観点からソート済み集合に B 木を採用しています [1].
B 木の仕組み
では,実際に B 木の中身がどうなっているのかを見ていきましょう!
B 木の定義
B 木には定義があり,この定義を満たすように挿入や削除を行うことで木の平衡を保つことができます.(よくわからない場合は飛ばして読み進めても大丈夫です)
B 木の定義
B 木
は,以下の性質をもつ根付き木です.(定義はアルゴリズムイントロダクション[1]に準拠しましたが,多少端折っている部分もあるので詳細はそちらを参照してください) T
各ノード
は以下の属性を持つ x
に格納されているキーの数 x (単に x.n のサイズともいう) x - 格納されている
個のキー x.n は昇順に並べられている x.\mathit{key}_1, x.\mathit{key}_2, \ldots, x.\mathit{key}_n が葉であれば x True
,内部ノードであればFalse
となるブール値x.\mathit{leaf} ノード
が内部ノードであれば, x 個のポインタ x.n+1 を持つ x.c_1, x.c_2, \ldots, x.c_{n+1} 各ノードについて,キー
と x.\mathit{key}_i の間にある子 x.\mathit{key}_{i+1} が持つ値 x.c_i は k_i x.\mathit{key}_i \le k_i \le x.\mathit{key}_{i+1} となる.(両端の子についても同様)
すべての葉は同じ深さを持つ
1 つのノードが格納できるキーの数には上限と下限が存在する.これは B 木の最小次数と呼ばれる値
を用いて表される.(最小次数は B 木 t~(t\ge 2) に固有の定数である) T
- 根を除くすべてのノードは少なくとも
個のキーをもつ.したがって,根を除くすべての内部ノードは少なくとも t-1 個の子をもつ.木が空でなければ根は少なくとも t 個のキーをもつ. 1 - どのノードも最大
個のキーを持つことができる.したがって,内部ノードは最大 2t-1 個の子を持つことができる.ちょうど 2t 個キーをもつ内部接点は飽和しているという. 2t-1
例
最小次数が
最小次数が
以下,上の
検索
B 木
アルゴリズム:
\text{B-Tree-Find}(T, k)
を x の根へのポインタで初期化する. T が葉でない間以下を繰り返す. x
の各キーについて順に, x
がキーより小さければ k をキーの左の子に更新して 2 に戻る. x がキーに一致すれば k True
を返す.が k のどのキーよりも大きければ x を x の最も右の子に更新する. x が葉である場合, x に x と等しいキーがあれば k True
,そうでなければFalse
を返す.
例
値
-
なので右の子に移動します.20 < 29
-
なので25 < 29 < 33 の左の子に移動します.33
-
のノードが見つかったので29 True
を返します.
挿入
次に挿入について考えます.B 木への挿入は,検索と同様に適切なノードをたどりながら行いますが,飽和したノードに挿入されないよう,ノードの分割を行いつつたどっていきます.
B 木
アルゴリズム:
\text{B-Tree-Insert}(T, k)
を x の根へのポインタで初期化する. T が葉でない間以下を繰り返す. x
が飽和していれば,ノードの分割を行う. x の各キーについて順に, x
がキーより小さければ k をキーの左の子に更新して 2 に戻る. x が k のどのキーよりも大きければ x を x の最も右の子に更新する. x - 葉への挿入でキー
を挿入する. k
ノードの分割,葉への挿入については以下のとおりです.
ノードの分割
- 小さい方から
個t-1 - 中央値
個1 - 大きい方から
個t-1
に分割します.小さい方から
葉への挿入(サイズが 2t-2 以下のとき)
ノードが葉であり,
葉への挿入(サイズが 2t-1 個のとき)
ノードが葉であり,ちょうど
そこで,ノードを分割してから挿入します.
例
値
- 右の子に進みます.
-
の左の子に進みます.33
-
すでに 5 個のキーを持っているので,ノードを分割します.
その後,
の左の子に進みます.30
-
の間に挿入します.27,29
→ これで挿入ができました!
削除
B 木
アルゴリズム:
\text{B-Tree-Remove}(T, k)
を x の根へのポインタで初期化する. T
その後,以下の場合分けにしたがう.
- キー
がノード k に存在し, x が葉であるとき, x を k から削除する x - キー
がノード k に存在し, x が内部ノードであるとき, x
における x の直前の子 k のサイズが y 以上のとき t
→の部分木の最大値 y を削除し, k' において x を k に置き換える k' における x の直後の子 k のサイズが z 以上のとき t
→の部分木の最小値 z を削除し, k' において x を k に置き換える k' , y のサイズがいずれも z のとき t-1
→をこの順で併合し,併合したノードから y,k,z を削除する k - キー
がノード k に存在しないとき,キー x を部分木に含むような k の子 x を特定する. x.c_i のサイズが x.c_i のとき,ステップ 3-1, 3-2 のいずれかを実行し, t-1 の適切な子に再帰する. x
のサイズが 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 のサイズが x.c_i であり,かつ, t-1 と x.c_{i-1} のサイズがどちらも x.c_{i+1} のとき t-1
→をどちらかの兄弟と併合する x.c_i
また,ノードの併合は次のように行います.
ノードの併合
ノード
では,B 木からの削除について実際にみていきましょう.
1. 葉からの削除
値
-
の右の子に進みます20
-
の左の子に進みます.30
-
を発見したので削除します.27
- これで完了です.
2-1. 内部ノードからの削除(左右のいずれかの子のサイズが t 以上)
値
-
の左の子に進みます.20
-
を発見しますが,そのまま消すことはできません.15
の左の子のサイズが15 以上なのでt ~(=3) の左の子から最大値15 を削除します.12
-
を削除し,その位置を先ほど取ってきた15 を入れて完了です.12
2-2. 内部ノードからの削除(左右の両方の子のサイズが t-1 以下)
値
-
の右の子に進みます.20
-
を発見しますが,そのまま消すことはできません.30
の左の子と右の子のサイズがともに30 なので,それらをマージします.t-1~(=2)
- マージされた頂点に進みます.
- マージされた頂点から値を削除します.
- これで完了です.
3-1/3-2. サイズが t-1 以下のノードに進む場合
値
- 根ノードの 2 つの子のサイズがともに
なので,これらをマージします.(3-2)t-1~(=2)
- マージが完了しました.
-
の左の子に進みますが,このノードのサイズは25 しかないのでそのままでは進めません.t-1
-
の右の子のサイズは25 以上なので,ここから最小値を削除します.t~(=3)
- 削除した最小値を左の子に移します.これで左の子のサイズが
以上になりました!t
の左の子に移動します.27
-
を削除します.22
- これで完了です!
まとめ
ここまで,
- B 木上の検索
- B 木への挿入
- B 木からの削除
について説明しました.
また,実装はこちらにアップロードしました:kentakom1213/rust-btree
各操作については,
をご覧ください.
動かして遊べるページも作ったのでぜひ試してみてください:B 木 - Rust Playground
参考文献
- 浅野哲夫.「アルゴリズムイントロダクション」第 3 版 第 2 巻,近代科学社,2012 年,p106-121
- B 木,Wikipedia,https://ja.wikipedia.org/wiki/B 木,2024 年 12 月 3 日閲覧
Discussion