[データ構造・アルゴリズム] B木について

質問

B木について分からないことがあるので教えて頂けたらありがたいです．

1. 平均で16個の子ノードのあるBツリーでは，100万件のデータにアクセスするとすると，最大何回のアクセスが必要になるか？また，その時に必要となる時間は何秒か？ハードディスクからのデータの転送時間は無視できるものとし，データはディスクの上にランダムに並んでいるものとする．
2. B木はメモリ上のデータへのアクセスよりは，外部記憶装置へのアクセスに適しているといわれている．その理由を簡潔に述べよ．
3. B木の1つのノードに格納できるキーの数を増やしていけば，データアクセスの効率はどうなっていくか？定性的に結果を推測せよ．

自分で考えた解答は
1. 10回
2. 探索がやりやすくなるから（よく分かりません・・・）
3. 良くなっていく（よく分かりません・・・）
なのですがどうでしょうか？真剣に分からないのでアドバイスなど良かったらお願いします！

回答No.2

Tacosan · ベストアンサー

1 はどっちなんだろう. 「100万件の中から 1件を見付ける」のかなぁ? いずれにしても「データにアクセスする回数」も曖昧だなぁ. 「アクセスするノード数」なら 16^k ≧ 10^6 を解けばよくって, 最大 5回のアクセスになります.
2: ディスクにアクセスするときは「セクタ」が単位になります. で, このセクタは通常 512バイトとかの値になり, この値にあわせてノードの大きさを決めることができる. 2分探索木ではノードが小さいが「セクタ単位でアクセスする」というディスクの特性から, ノードの大きさを適切に設定すれば「2分探索木でも B木でも 1個のノードにアクセスする時間は同じ」とすることができる. そうすれば, B木の方がアクセスするノード数が減るので高速にすることができる.
探索がやりやすいかというと, 実際にはあんまりやりやすいわけではないです.
3: データ数を n, キーの数を k とおくとアクセス効率は k log (n/k) に比例すると考えられる (キーの数が大きくなると 1個のノードが複数のセクタに分かれてしまうことがあり, このときにはアクセス時間はセクタ数に比例するとみなすことができる). 従って, 「データ数に応じた最適なキーの数」というのがあり, キーの数がそれより多すぎても少なすぎてもアクセス効率は悪くなる.

お礼

詳しくて丁寧な回答本当にありがとうございます！全く分からなかったので本当に助かりました、ありがとうございます！

回答No.1

Tacosan

１．問題があいまいです. 「100万件のデータにアクセスする」というのは,「(大きさ不明のデータの中から) 100万個のデータにアクセスする」のでしょうか, それとも「100万件のデータのある木から 1個のデータを見つける」のでしょうか? 必要な時間は求めるのに必要な値がまったく記されていないので無視.
２．外部記憶と主記憶とでは, 「データのアクセス単位」(つまり 1回のアクセスによって得られるデータ量) が異なります. B木におけるアクセスが「ノード」を単位とすることと組み合わせれば書けると思う.
３．目的とするデータにアクセスするために「アクセスするノードの個数」や「1個のノードにアクセスするための時間」は 1つのノードに格納できるキーの数に依存します. だから本当はこれらの値を評価すればいいんだけど, 定性的には「極端に少ないとき」と「極端に多いとき」でどうなりそうかが分かれば分かる, はず.

お礼

回答ありがとうございます、返事が遅れてすみませんでした。
時間をかけてよく考えてみたのですがやはり分からず……どうしたらいいでしょうか……