🌳

B Tree の制約の定義と次数

2025/01/16に公開

概要

書籍やネットの記事、大学のスライドを見ていると、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共通して下記の変数を用いる。
p: オーダ(=単一ノードの最大枝数, 子ノード数)

定義A 定義B
次数 この定義の次数を d, 最大キー数をq とすると、
d = \frac{q}{2}
d \in N (N は正の整数)
オーダ p に等しい [1]

d によって定義すると p = 2d + 1

p が奇数の場合 d = \frac{p-1}{2}
p が偶数の場合 d = \varnothing (\because d \in N)
最大枝数 2d + 1 p

pが奇数の場合
2d + 1
最小枝数 d + 1 \ulcorner\frac{p}{2}\urcorner

pが奇数の場合
\ulcorner\frac{2d+1}{2}\urcorner\ulcorner d + \frac{1}{2}\urcorner
d + 1 (\because d \in N)
最大キー数 2d

※ 必ず偶数になる
p - 1

pが奇数の場合
2d+1 - 1
2d
最小キー数 d \ulcorner\frac{p}{2}\urcorner - 1

pが奇数の場合
最小枝数 \ulcorner\frac{p}{2}\urcorner = d + 1より
\ulcorner\frac{p}{2}\urcorner - 1 = d

図表1 order と各制約の関係の例:

p (order, 最大枝数) d (定義Aの次数) 2d (定義Aの最大キー数) p-1 (定義Bの最大キー数) グラフ例
2 - - 1
3 1 2 2 2-3木
4 - - 3 赤黒木
5 2 4 4
6 - - 5
7 3 6 6

図表2:
p = 3, d = 1 のB Tree の例 (いわゆる2-3木)

以上から、異なるアプローチの定義でも、同じB木の制約となることがわかる。定義Aのほうは、必ず最大キー数が偶数になる。

脚注
  1. 増永[2017]「リレーショナルデータベース入門 第3版」, p.219 下部 †19 『p は木の各ノードからの出線(fan-out)数を規定する数であり,degree ともいう.』 ↩︎

Discussion