データ構造B木

平成28年秋季　問5．　データ構造B木

問題文「あるB木は、各節点に4個のキーを格納し、5本の枝を出す。このB木の根（深さのレベル0）から深さのレベル2までの節点に格納できるキーの個数は、最大で幾つか。」

で、いつものようにWikipediaさんを見てみるが、

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


実システムでも多用されており、データベース管理システムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木やB*木を使うことが多い）。

*********************************

ここまではなんとなくわかる気がする。

*********************************

多分岐の平衡木(バランス木)である。1 ノードから最大 m 個の枝が出るとき、これをオーダー m のB木という。後述する手順に従って操作すると、根と葉を除く「内部ノード」は最低でも m /2 の枝を持つことを保証できる・・・

*********************************

・・・外国語かっ( ﾟДﾟ)

で、色々とウェブサイトを探して理解ができるものを探したところ、プログラムなどの部分を考えなくてもわかるサイトを発見した。

B-treeインデックス入門
RDBMSで使われるB木を学ぼう

上の二つのサイトを交互に読むと、ある程度内容がわかるようだ。
まとめてしまうと、B-treeとは「検索のインデックス」であり、ある値を探す際に値とキー値を比較してキー値の方が大きくなった場合にその左側のポインタを見に行く検索方法のようだ。

ちょっと上のまとめもわかりにくいので、もっと具体的に書いてみると・・・


上の図で、例えば「17」という値を検索した場合、まず「16」と一番上の青い値（これがキー値というらしい）と比較して、17より大きな値「20」が見つかった時点で「20」の左下にある「16」というオレンジ色の行き先である「ポインタ」が示す次の「16」から「19」のかたまり（これがノードというらしい）を探しに行くということを繰り返して探しているもの見つける検索方法と言う風に言える。

本当は値は末端のリーフノードと呼ばれるノードのみが値を持つらしい。「17」というキー値（青色）の左側にある「17」というポインタ（オレンジ色）が指す「17」というリーフノード（赤色）に行きついて初めて値が見つかるという寸法のようだ。

このように作成されたインデックスをB-treeというのだそうな。

さて、ここで問題文に戻ると
問題文「あるB木は、各節点に4個のキーを格納し、5本の枝を出す。このB木の根（深さのレベル0）から深さのレベル2までの節点に格納できるキーの個数は、最大で幾つか。」
とあるので、

深さレベル0から2までのキーの個数は？と聞いているのだから
レベル0　⇒　4
レベル1　⇒　4×5
レベル2　⇒　4×5×5
の合計で「124」が正解となる。

ちなみに上の例で言うと、全検索をした場合の「17」を見つけるキー値との比較回数は順番に並んでいるとして「17」回になるが、B-treeで検索した場合は「20」を見つけるまでの4回と「17」を見つけるまでの2回で合計「6」回で検索できるということのように理解した。