B木について分からないことがあるので教えて頂けたらありがたいです.
1. 平均で16個の子ノードのあるBツリーでは,100万件のデータにアクセスするとすると,最大何回のアクセスが必要になるか?また,その時に必要となる時間は何秒か?ハードディスクからのデータの転送時間は無視できるものとし,データはディスクの上にランダムに並んでいるものとする.
2. B木はメモリ上のデータへのアクセスよりは,外部記憶装置へのアクセスに適しているといわれている.その理由を簡潔に述べよ.
3. B木の1つのノードに格納できるキーの数を増やしていけば,データアクセスの効率はどうなっていくか?定性的に結果を推測せよ.
自分で考えた解答は
1. 10回
2. 探索がやりやすくなるから(よく分かりません・・・)
3. 良くなっていく(よく分かりません・・・)
なのですがどうでしょうか?真剣に分からないのでアドバイスなど良かったらお願いします!
No.2ベストアンサー
- 回答日時:
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
- 回答日時:
1.問題があいまいです. 「100万件のデータにアクセスする」というのは,「(大きさ不明のデータの中から) 100万個のデータにアクセスする」のでしょうか, それとも「100万件のデータのある木から 1個のデータを見つける」のでしょうか? 必要な時間は求めるのに必要な値がまったく記されていないので無視.
2.外部記憶と主記憶とでは, 「データのアクセス単位」(つまり 1回のアクセスによって得られるデータ量) が異なります. B木におけるアクセスが「ノード」を単位とすることと組み合わせれば書けると思う.
3.目的とするデータにアクセスするために「アクセスするノードの個数」や「1個のノードにアクセスするための時間」は 1つのノードに格納できるキーの数に依存します. だから本当はこれらの値を評価すればいいんだけど, 定性的には「極端に少ないとき」と「極端に多いとき」でどうなりそうかが分かれば分かる, はず.
回答ありがとうございます、返事が遅れてすみませんでした。
時間をかけてよく考えてみたのですがやはり分からず……どうしたらいいでしょうか……
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Access(アクセス) スキルシートのエクセルの項目に 2 2023/04/04 22:41
- HTML・CSS WEBサイトの構築。表示データとWEBデザインを分離する考え方を専門用語・業界用語では何と言うか? 8 2022/09/27 09:16
- Excel(エクセル) エクセルで沢山のレコードの最後に追記するには? 7 2023/04/10 13:27
- 写真・ビデオ スマホアプリ 写真データへのアクセスについて 情報漏洩 2 2023/06/22 23:00
- VPN VPNは設定した方がいいですか? VPNには常時接続するべき? 1 2023/05/25 17:43
- 写真・ビデオ チャットアプリと写真データ漏洩 プライバシーについて 1 2023/06/19 20:59
- その他(クラウドサービス・オンラインストレージ) このような条件でデータを置いておけるサービス 3 2022/07/25 08:31
- 写真・ビデオ チャットアプリと写真データ 漏洩やプライバシーについて 1 2023/06/19 03:28
- その他(IT・Webサービス) チャットアプリと写真データ 漏洩やプライバシーについて 6 2023/06/19 06:04
- 写真・ビデオ iPhoneのプライバシーとセキュリティの写真の項目について 2 2023/06/24 23:11
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
CPUの考え方を教えてください ...
-
昔Winnyってありましたけど、あ...
-
2分探索木の高さを求めるプロ...
-
同じタグ名の項目取得
-
VB6.0でDOMを使用して...
-
TreeViewについて
-
ToolStripMenuItemの選択(VB)
-
あるノードリストに、特定の名...
-
SNMP リンクダウンとノードダ...
-
XML文書の指定した属性値を持つ...
-
ルート要素ノードが2個ある場合?
-
ノード数とは?
-
ナップザック問題で複数の経路...
-
C# TreeView 効率良いノード追...
-
XMLで特定の兄弟のノードの数を...
-
ツリービューを閉じさせたくない。
-
カウントアップ
-
特殊記号が勝手にエスケープさ...
-
eclipseへのxmlファイル追加
-
東芝のDynabookなのですがアン...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
CPUの考え方を教えてください ...
-
昔Winnyってありましたけど、あ...
-
SNMP リンクダウンとノードダ...
-
ルート要素ノードが2個ある場合?
-
同じタグ名の項目取得
-
あるノードリストに、特定の名...
-
ノードとは
-
TreeView の初期表示について
-
ツリービューのノードをダブル...
-
ノード数とは?
-
コンテキストメニュークリック...
-
XML文書の指定した属性値を持つ...
-
C#でtreeviewの指定ノードを選...
-
複数のマックPCによる数値計算...
-
VB6.0ツリービューについて
-
TreeViewの再表示のちらつきを...
-
VB6.0でDOMを使用して...
-
vbsのDOMDocumentで要素のText...
-
TreeViewで複数ノードの選択は...
-
C# TreeView 効率良いノード追...
おすすめ情報