木・グラフ・ハッシュは、DB の索引・ファイルシステム・Web のリンク構造・キャッシュなど、現代のシステムを支える基礎構造です。
鳴海 理央
木 は親子関係を持つ階層構造で、二分探索木 は左部分木 < 親 < 右部分木 という性質を持ちます。
平衡が取れていれば探索は O(log n)。
砂原 ニコ
B木って何がいいの?
緒方 ナオミ 先生
B木 は1ノードに複数キーを持てるので、ディスクの1回読みで多くのキーを処理できる。
だから DB のインデックスはほぼ B木 (or B+木) なの。
鳴海 理央
B+木 は葉ノードに全キーを持ちつつ葉同士をリンクするので、範囲検索 (BETWEEN) が高速です。
AP科目Aで B木と B+木の違いを聞かれることがあります。
藤咲 まりあ
グラフ と ハッシュ は…?
鳴海 理央
グラフは頂点と辺。
SNS の繋がりや交通網のモデル化に使い、深さ優先探索 と 幅優先探索 で巡回します。
ハッシュはキーから固定長の値を作る関数で、ハッシュテーブル は平均 O(1) の検索を実現します。
緒方 ナオミ 先生
ハッシュは衝突対策 (チェイン法・開番地法) もよく問われるところね。
一通り目を通しておきましょう。
確認クイズ
B+木 が B木 と比較して優れている点として、最も適切なものはどれか。
- 1ノードに格納できるキーの最大数が大きい
- 葉ノード同士がリンクされており、範囲検索が高速である
- 挿入・削除のコストが常に O(1) である
- 重複キーを許容する点で柔軟である
こたえを見る
正解: 2. 葉ノード同士がリンクされており、範囲検索が高速である
B+木は葉ノードに全キーを持ち、葉同士をリンクポインタで連結するため、範囲検索 (BETWEEN・ORDER BY) が B木 より高速です。1ノードのキー数や挿入コストはどちらも同等です。