平成18年春期試験問題 午前問9

データ構造に関する記述のうち,B木の説明として適切なものはどれか。

  • ある特定のアルゴリズムに従って,レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。
  • 索引部の各ノードのキー値を中心にして,小さい側のレコード数と大きい側のレコード数の比率が,ある範囲内に収まるように動的に再配置しながら格納する。
  • レコードの物理的配置とは独立に,論理的にレコードをつなぐポインタによって,レコードを関係づけて格納する。
  • レコードをキー値の昇順にしてトラックなどのアクセス単位(ページ)ごとに格納し,各ページ内の最大キー値とそのページの番地をもつ索引を作る。
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:データ構造
解説
B木は、木構造内のノードの容量の尺度である次数kを基準にして下記の特徴をもつ多分木です。
  • 根は1以上2k個以下のキーをもつ
  • 根以外の節はk以上2k個以下のキーをもつ
  • 根から全ての葉までの深さが同じである
09.png
B木の各節は保持するキー数+1個のポインタをもちます。

k次のB木では、節点が持てる子の数が"k以上2k以下"という特徴があり、データの挿入や削除が行われた場合には、この範囲内に収まるように動的再構成が行われます。
  • ハッシュ法の説明です。
  • 正しい。
  • リスト構造の説明です。
  • 索引編成ファイルの構造についての説明です。

この問題の出題歴


Pagetop