B+木インデックスでDBの検索効率

応用情報技術者平成30年秋期 午前問29

"部品"表のメーカコード列に対し，B+木インデックスを作成した。これによって，検索の性能改善が最も期待できる操作はどれか。ここで，部品及びメーカのデータ件数は十分に多く，"部品"表に存在するメーカコード列の値の種類は十分な数があり，かつ，均一に分散されているものとする。また，"部品"表のごく少数の行には，メーカコード列にNULLが設定されている。実線の下線は主キーを，破線の下線は外部キーを表す。

１、B+木インデックスは、
木の深さが一定で葉のみが値をもつ平衡木を用いたインデックスで、RDBMSのインデックス法として現在最も普及しています。

B+木は、根および節にはキー値の範囲と下層のブロックへのポインタ、葉にはキー値と表内の行の位置情報と前後の葉へのポインタが格納されていて、根から節をたどっていくことで目的のデータを検索します。すべてのキー値が同じ深さにあるので、データ量が増加してもパフォーマンスの低下が少なく、どのキー値に対してもランダム検索や範囲検索、挿入・更新・削除を効率よく行える特徴を持ちます。また葉に含まれている前後の葉へのポインタによって一致検索だけでなく、"<"，">"，"BETWEEN"などの範囲検索を効率よく行えます。

しかし
・データの分布に偏りがある
・NULL値
・否定を含む
検索条件では効果を発揮できません。

なぜ上記検索条件であると効果を発揮できないとは、全てスキャンするですからね。
連続な範囲を確定できれば、効果を発揮できるとこのとですね。

参考：
https://www.ap-siken.com/kakomon/23_aki/q32.html