m分木（m-aryツリー）とは？定義・m-way探索木の条件・B木との関係を解説

コンピュータサイエンスにおけるm分木（m-ary tree）とは、ノードの集合を階層的に表現したデータ構造であり、一般的に次のように定義されます。

• 木は根（ルート）ノードから始まる。
• 木の各ノードは、子ノードへのポインタのリストを保持している。
• 各ノードが持てる子ノードの数はm以下である。

m分木の典型的な実装では、子ノードを格納するためにm個の参照（ポインタ）からなる配列を使用します。ここで、mは子ノード数の上限値（最大値）である点に注意してください。実際の子の数がmより少ない場合は、未使用のスロットが生じます。

m分木の構造イメージ

m-way探索木の条件

m-way探索木（m-way search tree）は、以下のいずれかを満たす木として定義されます。

1. 木が空である、または
2. 木が、b個（1 ≦ b < m）のキー k₁, k₂, …, k_b と、b+1個の部分木 T₀, T₁, …, T_b（a = 0..b） を持つ根から構成され、かつ次の条件をすべて満たす。

• kが T₀ 内のキーであるならば、k ≦ k₁
• kが T_a（0 < a < b）内のキーであるならば、k_a ≦ k ≦ k_{a+1}
• kが T_b 内のキーであるならば、k > k_b
• すべての T_a が非空のm-way探索木であるか、あるいはすべての T_a が空である。

この条件により、m-way探索木では各ノードのキーの順序と部分木の配置に規則性が保たれ、効率的な探索が可能になります。

完全m分木の高さ

n個のノードを持つ完全m分木の高さは、次の式で表されます。

高さ = ⌈log_m n⌉（log_m n の天井値）

この式は、m分木が二分木よりも多くの子を持てる分だけ、同じノード数でも木の高さを低く抑えられることを示しています。高さが小さいほど、根から葉までのアクセス回数が減り、探索効率が向上します。

B木（B-tree）との関係

次数mのB木（B-tree）は、m-way木の一種であり、さらに次の条件を満たします。

• すべての葉ノードが同じレベル（深さ）に存在すること。
• 根および葉以外のすべてのノードは、最小 m/2 個、最大 m 個の子を持つこと。
• 根は、最小 2個、最大 m個の子を持つこと。

B木はこれらのバランス条件を満たすことで、常に均整の取れた木構造を維持し、データベースやファイルシステムなど、大量のデータを扱う場面で広く活用されています。