多分岐木の基礎と代表的な木構造の比較：M-ary木・B木・B+木・Trie・決定木まで詳しく解説
エバープレイ編集部多分岐木とは — 定義と概念
多分岐木（たぶんきぎ、multiway tree / m-ary tree）は、各ノードが2つ以上の子ノードを持つことが許される木構造（ツリー構造）の総称です。一般的な二分木（各ノードが最大2つの子を持つ）を拡張したもので、「k分岐木」「m分岐木」などとも呼ばれます。多分岐木は「各ノードが持ちうる子の最大数」をパラメータに持つことが多く、このパラメータにより挙動や用途が異なります。
代表的な種類
M-ary（m分岐）木：各ノードが最大m個の子を持つ一般的な多分岐木。二分木はm=2の特殊例。
B木（B-tree）：データベースやファイルシステムで広く使われる平衡多分岐探索木。1ノードで多数の子・鍵を保持し、ディスクI/Oを効率化する設計（各ノードはある範囲の鍵数を持ち、分割・併合により高さを抑える）。
B+木：B木の派生で、すべての値が葉に格納され、内部ノードは索引用に限定される。レンジ検索が高速でデータベースインデックスで多用される。
Trie（接頭辞木、プレフィックス木）：文字列探索に特化した多分岐木。各エッジやノードが文字（または文字集合）を表し、共通接頭辞の共有で検索を高速化する。分岐数はアルファベットサイズなどに依存する。
決定木（Decision Tree）：機械学習で使われる多分岐木。ノードの分割基準によって複数分岐することがある（カテゴリ変数の分岐など）。目的は分類や回帰。
基本的な性質と概念用語
次数（degree）・分岐数：ノードが持つ子の数。ツリー全体の最大子数をmと定めることがある。
高さ（height）と深さ（depth）：ルートから葉までの距離。多分岐木でもバランスが取れていれば高さは小さく、探索が高速になる。
葉（leaf）と内部ノード：子を持たないノードが葉。葉の扱い（データ格納の可否）は木の種類で異なる（B木は内部にもデータを置く場合があるが、B+木は葉に集中）。
完全多分岐木：すべての内部ノードがちょうどm個の子を持ち、すべての葉が同一深さにあるような理想形。
実装方法（メモリ表現の選択）
多分岐木の実装は用途や分岐数により最適な方法が異なります。代表的な表現を挙げます。
配列（固定分岐）：完全なm分岐木を表現する際、子ポインタを固定長配列（size m）で持たせる手法。高速だが、分岐が少ない場合に無駄なメモリを消費する。
可変長リスト（動的）：各ノードが可変長の子リスト（リンクリストやベクタ）を持つ方法。メモリ効率は良いがランダムアクセスで若干コストが増す。
左子・右兄弟表現（left-child right-sibling）：任意分岐の木を二分木に変換して扱う手法。各ノードは「最初の子」と「次兄弟」を持つだけで済み、二分木用アルゴリズムが利用できる利点がある。
ディスク・ページベース（B木など）：ノード（ページ）に多数の鍵と子ポインタを格納し、ディスクI/Oを最小化するよう設計する。データベースインデックスに最適化される。
主要操作と計算量の概観
具体的な計算量は木の種類と実装に依存しますが、一般的な考え方を示します。
探索（search）：バランスが取れている多分岐木では高さがO(log n)（基数は分岐数に依存）に抑えられるため、1ノードあたりの比較コストをcとすると全体でO(c · log_m n)。B木では1ノード内で複数の鍵を線形／二分探索し、ディスクアクセス数は高さに比例します。
挿入・削除：B木のような平衡多分岐木では分割（split）や併合（merge）、借用（borrow）操作が必要になり、最悪O(h)（hは高さ）。Trieではキー長kに依存してO(k)。
走査（traversal）：全ノード訪問は当然O(n)。前順・後順の拡張は「各子を順に訪れる」形で一般化できる。
応用分野
データベース・インデックス：B木／B+木はディスクページのI/O効率を最大化するために設計され、多くのRDBMSやファイルシステムで利用される。
ファイルシステム：ディレクトリ構造やメタデータ管理に多分岐木が使われることがある（例：B木ベースのディレクトリインデックス）。
文字列検索と自動補完：Trieは接頭辞検索、オートコンプリート、辞書実装で強力。各分岐が文字集合の大きさ（アルファベットのサイズ）に対応する。
XML/HTML DOM：ツリー構造そのものが任意分岐であり、DOMツリーは多分岐木として扱われる。ノード挿入・削除、走査を頻繁に行う。
機械学習（決定木）：ノードで条件分岐を行うことで分類・回帰を行う。分岐数はカテゴリの分割方法やアルゴリズムで変わる。
設計上の注意点とトレードオフ
分岐数の選定：分岐数が大きいほど高さは低くなりやすいが、各ノードの管理コスト（比較・メモリ）が増える。ディスクベースでは「ページサイズに応じた分岐数」が重要。
バランスの保持：検索性能を安定させるにはバランスが必要。B木系は自動でバランスを保つが、一般の多分岐木では明示的な平衡化が必要な場合がある。
メモリ対I/O：主記憶での高速アクセスを重視するか、外部記憶（ディスク/SSD）でI/Oを抑えることを重視するかでノードの設計が変わる。
可変長データと断片化：ノードが可変長データを持つ場合、メモリ断片化や実装の複雑さが増す。特にディスク上ではページ分割・再配置のコストが問題になる。
並列化とロック：高スループット環境では部分的ロックやロックフリー設計が求められる。B木系ではページレベルのロック戦略やコピーオンライト戦略（COW）が使われる。
実例・簡単な表現（視覚化）
以下は3分岐木（各ノードが最大3子）を簡易的に表した例です。
- root
- child A
- grandchild A1
- grandchild A2
- child B
- child C
- grandchild C1
- child A
このように多段に分岐する構造が、木構造の直感的な表現です。
よくある誤解
「多分岐木＝無条件に高速」ではない：分岐数や内部ノードの探索コスト、キャッシュやI/O特性によっては逆に遅くなることがある。
「Trieは常に省メモリ」でもない：アルファベットが大きい場合、各ノードの分岐表現でメモリを多く消費する。圧縮Trie（例：Radix Tree）などの工夫が使われる。
まとめ（実務での選び方ガイド）
多分岐木は用途に応じて多様な実装・最適化が可能です。キー選択の指針は次の通りです。
大量データでディスクI/Oがボトルネック：B木／B+木を検討する。
文字列検索・オートコンプリート：Trie（やRadix Tree）。
ツリー構造の汎用表現が欲しい：左子右兄弟変換や可変長子リストを検討。
機械学習用途：決定木のアルゴリズム（CART、ID3など）を利用し、過学習対策や剪定を行う。
設計時は「分岐数」「ノード内処理コスト」「メモリ/ディスクのトレードオフ」「並列性」を総合的に見て選択することが重要です。
参考文献
- 木 (データ構造) — Wikipedia（日本語）
- M-ary tree — Wikipedia（英語）
- B-tree — Wikipedia（英語）
- B+ tree — Wikipedia（英語）
- Trie（接頭辞木） — Wikipedia（日本語）
- Left-child right-sibling binary tree — Wikipedia（英語）
- Decision tree learning — Wikipedia（英語）
投稿者プロフィール
