対話型シミュレーター
B-tree インデックス探索コストと階層数シミュレーター
木構造、階層コスト、範囲走査の増え方を並べ、索引設計で何が効くかを確認します。
パラメータ入力
一時停止中はスライダーを動かすと結果が即座に更新されます。
物理モデルと主要式
$$h=\lceil\log_f N\rceil$$
B-treeの高さは行数Nと分岐数fの対数で決まります。点検索は高さが支配的ですが、範囲走査では一致行数とページ局所性も効きます。
読み取り方
木構造図では分岐数が増えるほど高さが下がります。
コスト図ではページ読み込み時間が全体遅延に直結します。
範囲走査図では選択率が上がると葉ページ走査が支配的になります。
会話で学ぶB-tree インデックス探索コストと階層数
🙋B-tree インデックス探索コストと階層数では、まずどこを見ればいいですか？行数 Nを動かすと図も数値も同時に変わるので、少し迷います。
🎓最初はB-tree高さを見ます。ただし数字だけで判断せず、B-tree階層模式図で前提の形や状態を確認し、点検索コストで分布や変化の出方を合わせて読みます。木構造図では分岐数が増えるほど高さが下がります。
🙋行数 Nを大きくするとB-tree高さが変わりそうなのは分かります。では、分岐数 fはどのくらい効いていると考えればいいですか？
🎓分岐数 fを少しずつ動かして点検索コストの動きを見ると、支配している項が見えてきます。B-treeの高さは行数Nと分岐数fの対数で決まります。点検索は高さが支配的ですが、範囲走査では一致行数とページ局所性も効きます。 1点の計算で終わらせず、実際にばらつきそうな範囲を往復させるのが大事です。
🙋範囲走査コストは何を見るための図ですか？普通のグラフだけでも判断できそうに見えます。
🎓範囲走査コストは、危険側に入る境界や、余裕が急に崩れる組み合わせを探すための図です。コスト図ではページ読み込み時間が全体遅延に直結します。 例えばDBインデックス設計の初期見積もりでは、単一点の値より「少し条件がずれたらどうなるか」が効きます。
🙋では、B-tree高さが基準内なら、この条件をそのまま採用してよいですか？
🎓ここでは初期検討として扱います。SSD/HDDやキャッシュ条件の影響比較や点検索と範囲検索のボトルネック整理には役立ちますが、最終判断では規格値、実測値、詳細解析、メーカー条件で確認してください。範囲走査図では選択率が上がると葉ページ走査が支配的になります。
実務での使い方
DBインデックス設計の初期見積もり。
SSD/HDDやキャッシュ条件の影響比較。
点検索と範囲検索のボトルネック整理。
よくある質問
B-tree高さと点検索コストを先に見ます。次にB-tree階層模式図で前提の状態を確認し、点検索コストで分布や変化の偏りを読みます。木構造図では分岐数が増えるほど高さが下がります。
行数 Nを単独で動かしたあと、分岐数 fも同じ幅で動かしてB-tree高さの変化量を比べます。範囲走査コストを見ると、どの組み合わせで余裕や性能が急に変わるかを把握できます。
DBインデックス設計の初期見積もりに使います。単一点の数値ではなく、入力範囲を少し広げてB-tree高さの余裕が保てるかを確認すると、詳細解析へ進む前の論点整理に役立ちます。
B-treeの高さは行数Nと分岐数fの対数で決まります。点検索は高さが支配的ですが、範囲走査では一致行数とページ局所性も効きます。最終判断では規格値、実測値、詳細解析、メーカー条件を確認してください。
使い方ガイド
- レコード総数（rows）を入力します。例：1000万件のテーブルの場合、10000000を指定
- ノードあたりのポインタ数（fanout）を設定します。一般的なディスク型B-treeは100～500、メモリ型は50～200が目安です
- ディスク読取時間（readMs）をミリ秒で入力します。SSD環境では0.1～1ms、HDD環境では5～10msが実測値
- 選択率（selectivity）を % 単位で指定します（例：5% なら 5 と入力）。WHERE句の条件で返すレコード比率です
- シミュレート実行で、B-tree高さ・点検索コスト・範囲走査コストが計算されます
具体的な計算例
5000万件のユーザーテーブルで、顧客ID（プライマリキー）によるB-treeインデックスを構築した場合を想定します。fanout=256、readMs=0.5msの条件では、B-tree高さ=4層となります。点検索（1件取得）のコスト＝4×0.5ms=2.0msです。一方、city='Tokyo'で5%の範囲走査（選択率=5、一致行数250万件）を実行する場合、リーフノード走査によるコスト＝(250万÷256)×0.5ms≈4900msとなり、フルテーブルスキャンとの比較が必要になります。
実務での注意点
- fanout値はページサイズとキーサイズに依存します。8KBページで8バイトキー+8バイトポインタなら約400ポインタが理論値ですが、ノード分割オーバーヘッドで実効値は60～70%に低下します
- readMsは単なるI/O時間ではなく、キャッシュヒット率やSQLプランナの判断を含めて見積もります。SQLiteメモリDB＝0.001ms、PostgreSQL SSD＝0.2ms、Oracle HDD RAID5＝8msが実例です
- selectivityが0.1を超える場合、インデックスリーフ走査が増加し、ランダムアクセスシーケンシャルスキャンより遅くなるため、テーブル全スキャンへの切り替えを検討してください
- 複合インデックス（4カラム以上）の場合はfanoutが指数関数的に減少するため、別途キー圧縮設計が必要です