B+木インデックス

問題

応用情報技術者平成29年春期午前問28

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

　部品(部品コード，部品名，メーカコード)
　メーカ(メーカコード，メーカ名，住所)

メーカコードの値が1001以外の部品を検索する。
メーカコードの値が1001でも4001でもない部品を検索する。
メーカコードの値が4001以上，4003以下の部品を検索する。
メーカコードの値がNULL以外の部品を検索する。

答え

メーカーコードの値が4001以上、4003以下の部品を検索する

解説

B＋木は、葉ノードにのみデータを保持しまた葉ノードをポインタでリンクすることで、範囲検索が B木より速く行うことができます。

2分探索木→AVL木→B木→B⁺木と、以下のスライドが大変分かりやすいです。

これでわかるB-treeアルゴリズム / B-tree algorithm

B木

B木とは、’Balanced Tree’ でそのまま「平衡木」です。

2分探索木の平衡木にはAVL木がありますが、Ｂ木は2分木構造ではなく多分木構造で自動的に平衡を保つ木構造です。

B木（びーき）は、コンピュータサイエンスにおけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

B+木

B+木は、葉ノードにのみデータを格納するB木です。

B+木（英: B+ tree）は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント（「ブロック」などと呼ばれる。木構造におけるノードに相当）にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層（葉ノード）に格納され、内部ノードにはキーのみが格納される。

出典: フリー百科事典『ウィキペディア（Wikipedia）』