🌳
B Tree の制約の定義と次数
概要
書籍やネットの記事、大学のスライドを見ていると、B Tree (B木) の定義の仕方が2種類あることに気づいた。定義の違いに言及している記事があまりなかったため個人的に整理するためにまとめた。挿入や削除のアルゴリズムを考える際に定義の理解が必要となるため覚えておきたい。数式でイメージを掴むことに重きを置いており、数学的な厳密さは考慮していない。
最初に結論を述べると、どちらも同じ制約を持ったB木を作成できる。
片方の定義はより厳密な定義で、もう片方は最大キー数を偶数に固定することで論理展開がわかりやすくなっているという特徴がある。
詳細
ざっくりと下記の定義のやり方がある。
定義A | 定義B | |
---|---|---|
方法概要 | <単一ノードに入る最大キー数> ÷ 2 を次数とし、次数をベースに定義する方法 (この定義では最大キー数が必ず偶数になる) |
order によって定義する方法 (order を次数 (degree) と呼ぶ文献もある) |
例 | 佐賀大学講義スライド, IT Media Delphiアルゴリズムトレーニング 第5回 RDBMSで使われるB木を学ぼう | リレーショナルデータベース入門 第3版(増永 2017), wikipedia |
以下、定義によって決まる B Tree の各ノードと枝数(fanout)の制約について表形式でまとまる。
A, B共通して下記の変数を用いる。
定義A | 定義B | |
---|---|---|
次数 | この定義の次数を |
オーダ |
最大枝数 |
→ |
|
最小枝数 |
→ → |
|
最大キー数 |
※ 必ず偶数になる |
→ → |
最小キー数 |
最小枝数 |
図表1 order と各制約の関係の例:
|
|
|
|
グラフ例 |
---|---|---|---|---|
2 | - | - | 1 | |
3 | 1 | 2 | 2 | 2-3木 |
4 | - | - | 3 | 赤黒木 |
5 | 2 | 4 | 4 | |
6 | - | - | 5 | |
7 | 3 | 6 | 6 |
図表2:
以上から、異なるアプローチの定義でも、同じB木の制約となることがわかる。定義Aのほうは、必ず最大キー数が偶数になる。
-
増永[2017]「リレーショナルデータベース入門 第3版」, p.219 下部 †19 『
は木の各ノードからの出線(fan-out)数を規定する数であり,degree ともいう.』 ↩︎p
Discussion