二分探索とBツリーの比較回数・階層計算
意味・解説
データ件数 $n$ に対して、枝分かれ数（オーダー）の違いが探索の深さ（比較回数）に与える影響を数理的に比較すること。
二分探索は $\log_2 n$、オーダー $m$ のBツリーは $\log_m n$ の階層（深さ）を持つ。分岐数 $m$ を増やすほど、目的のデータに到達するためのアクセス回数は劇的に減少する。
くわしく
「情報の『住所録』の階層をどれだけ低くできるか」の計算です。
1.二分探索：
常に2択のため、100万件なら約20回の比較が必要です。
2.Bツリー：
例えば1つのノードから100個に枝分かれする場合、100万件のデータもわずか3回のアクセス（$\log_{100} 1,000,000 = 3$）で見つかります。ポイントは、ハードディスクのような「読み出しが遅い」装置からデータを引く際、このアクセス回数を1回でも減らすことがシステム全体の爆速化に直結するからです。
例文
大規模データベースの索引設計において、探索深度を最小化するためにBツリーのオーダーを調整し、二分探索よりも格段に少ないディスクアクセス回数を実現した。
同義語: 探索深度の比較
分類: アルゴリズムの効率性分析