1件ずつ探す？ 索引で探す？
番号の付いたデータを、先頭から探す方法と、案内をたどる方法で比較します。
やってみよう「1手進める」を押して、2つの探し方を見よう。
どこを見る？ 比較するキーの数と、たどるページの数は別に数えます。
なぜ、そうなる？
本の索引は、本文を最初から読む代わりに、探す言葉のあるページへ案内してくれます。データベースの索引も、探す値からデータの場所を絞ります。
ここでは1ページに最大4方向の案内を持つ小さなB+木を、実際に組み立てて検索します。索引は別に作っておく必要があり、追加や変更にも手間がかかります。
ひとことで
索引は「先に整理しておく手間」と引き換えに、探す範囲を絞る。結果だけでなく、操作の前後で何が変わったかを説明してみましょう。
ことばを確認する
- キー
- 探す手がかりになる値。ここでは番号。
- B+木
- 案内が枝分かれし、いちばん下にキーを並べた索引。
- ページ参照
- ひとまとまりの案内・データを見ること。
計算のしくみと、この模型の限界
固定データを一括構築した分岐数4・葉容量4のB+木です。ページ内は順に比較します。線形検索は一意キーの一致で停止します。比較回数は実測の待ち時間やディスクI/Oではなく、索引作成・更新、キャッシュ、物理装置の性能は比較に含みません。
線形検索は配列の先頭から等値比較。B+木は区切りキーとの比較で子を選び、葉で一致を調べます。表示する回数は、この処理で実際に数えた値。
出典・関連する記事
参照資料と、画面で計算する教材モデルは区別しています。情報の確認日：2026年9月22日。