問題
データ構造に関する記述のうち，B木の説明として適切なものはどれか。
- ある特定のアルゴリズムに従って，レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。
- 索引部の各ノードのキー値を中心にして，小さい側のレコード数と大きい側のレコード数の比率が，ある範囲内に収まるように動的に再配置しながら格納する。
- レコードの物理的配置とは独立に，論理的にレコードをつなぐポインタによって，レコードを関係づけて格納する。
- レコードをキー値の昇順にしてトラックなどのアクセス単位(ページ)ごとに格納し，各ページ内の最大キー値とそのページの番地をもつ索引を作る。
答え
索引部の各ノードのキー値を中心にして，小さい側のレコード数と大きい側のレコード数の比率が，ある範囲内に収まるように動的に再配置しながら格納する。
解説
B木
B木（びーき）は、コンピュータサイエンスにおけるデータ構造、特に木構造の一つ。ブロック単位のランダムアクセスが可能な補助記憶装置（ハードディスクドライブなど）上に木構造を実装するのに適した構造として知られる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
実システムでも多用されており、データベース管理システムの多くはB木による索引を実装している（B木の改良型または亜種であるB+木やB*木を使うことが多い）。
B木は以下の条件を満たす多分探索木で、データの挿入や削除で条件を満たさなくなる場合は自動的に木の高さを調節する平衡木です。
- 各ノードは最大で m 本の枝を持つ(m≧3)
- 根と葉を除く各ノードは [m/2] 本以上の枝を持つ
- 枝と枝の間には要素が１つあり、各要素は昇順に整列されている
- 各ノードの左端の要素 a の左の枝の先には a より小さい要素がある
- 各ノードの右端の要素 a の右の枝の先には a より大きい要素がある
- 各ノードの要素 a, b (a < b) の間の枝の先には a より大きく b より小さい要素がある
- 全ての葉から根までのパス上のノード数は等しい
「 索引部の各ノードのキー値を中心にして，小さい側のレコード数と大きい側のレコード数の比率が，ある範囲内に収まるように動的に再配置しながら格納する。 」
ハッシュ関数
ハッシュ関数 (ハッシュかんすう、英: hash function) あるいは要約関数[1]とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことを要約値やハッシュ値または単にハッシュという。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
「ある特定のアルゴリズムに従って，レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。」
連結リスト
連結リスト（れんけつリスト、英語: Linked list）は、最も基本的なデータ構造の1つであり、他のデータ構造の実装に使われる。リンクリスト、リンクトリストとも表記される。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
一連のノードが、任意のデータフィールド群を持ち、1つか2つの参照（リンク）により次（および前）のノードを指している。連結リストの主な利点は、リスト上のノードを様々な順番で検索可能な点である。連結リストは自己参照型のデータ型であり、同じデータ型の別のノードへのリンク（またはポインタ）を含んでいる。連結リストは場所が分かっていれば、ノードの挿入や削除を定数時間で行うことができる（場所を探すのにかかる時間はリスト上の順番の条件などにも依存するし、後述する片方向リストなのか双方向リストなのかにも依存する）。連結リストにはいくつかの種類があり、片方向リスト、双方向リスト、線形リスト、循環リストなどがある。
「レコードの物理的配置とは独立に，論理的にレコードをつなぐポインタによって，レコードを関係づけて格納する。」
索引順編成ファイル
インデックスと言う「索引」がついたファイルでレコードアドレスを検索する際に索引で指定してアクセスする編成法である。アクセス方法は3種類全部が可能である。構成としては以下の通りである。
it-資格.jp
・基本データ域(プライム領域) データを格納する
・索引域(インデックス領域) 索引を格納する。「マスタ索引」→「シリンダ索引」→「トラック索引」の順に索引される。
・あふれ域(オーバフロー領域) 基本データ域にデータが格納されなくなった時に使用する。これは2種類ある。
「シリンダあふれ域」 各トラックからあふれたレコードを格納する。
「独立あふれ域」 シリンダあふれ域が一杯になったら使用する。
「レコードをキー値の昇順にしてトラックなどのアクセス単位(ページ)ごとに格納し，各ページ内の最大キー値とそのページの番地をもつ索引を作る。」