４．１ファイル編成

データベーススペシャリスト試験の教科書より、ファイル編成について学習した内容をまとめ。

ファイル編成とは

DBMS、特にRDBMSで用いられるファイル編成は大きく三つ。

• ヒープファイル
• 順次編成ファイル
• ハッシュファイル

記憶階層と磁気ディスク

１次記憶（primary storage）CPUから直接アクセスされる記憶装置。主記憶（main storage）、アクセス早い、記憶容量は小さい、電源切ると記憶内容がなくなる揮発性記憶（volatile storage）

２次記憶（secondary storage）磁気ディスク、SSD、光ディスク（CD、DVD）、磁気テープ、アクセス遅い、記憶容量は大きい、電源切っても記憶内容残る不揮発性記憶（non-volatile storage）

ブロック（またはページ）という単位で磁気ディスクとの間で読み込み行う。正確にはブロック（block）とページ（page）は別の概念。ブロックはDBMSあるいはアクセス方から見た入出力単位、連続したレコードのかたまり。一方ページは仮想記憶法域のコンピュータにおけるメモリの分割単位。OSは一般にこのページ単位でディスクに入出力を行う。一つのブロックにいくるの（固定長）レコードが格納されるかを表すものをブロック化因子（blocking factor）という。一般的に可変。一般にはブロックサイズ＞ページサイズ

ファイル編成（file organization）

利用者が選択できる範囲はインデックスの種類とインデックスを付けるかどうか。

ファイルはレコードの集合、レコードは一つのフィールドから成り立つ。

アクセス法（access method）はファイルのレコードをどう位置決めし、読み書きするかを示すもの。

RDBMSが一般化する前のメインフレーム時代のファイル編成は、順次ファイル、索引順次ファイル、直接編成ファイル。現在はヒープファイル、順次ファイル、ハッシュファイル（直接編成ファイルの一種）などと分類。

ヒープファイル（heap file）

ヒープ＝積み重ねる。原始的なファイル。非順序ファイル（unordered file）とも呼ぶ。アクセス方法は線形探索（linear search）、二次インデックス。

線形探索とはヒープファイルのページを順番にたどって目的のレコードを見つけることで、一つのレコードを見つけるには平均して（総ページ／２）回ページを読み込み必要。

順次ファイル（sequential file）

順序ファイル（ordered file）、キーの順番（昇順、降順）にレコード格納、２分探索（binary search）の手法も使える

順次アクセスとキーによる直接アクセスを可能にしたのが、IS（indexed sequential）ファイル（索引順次ファイル）

ハッシュファイル（hash file）

ハッシュ関数を適用し、レコードの格納位置を決めるファイル。ハッシュ関数を適用するフィールドをハッシュフィールドで通常は主キー。レコードが格納されるブロック（これをハッシュバケット（hash bucket）という）単位のアドレスであり、レコードにアクセスするにはブロックを主記憶に読み込んだ後、線形探索などを行う