第７章データベース管理システム７．１データベース管理システムの概要７．２データベースの格納方式７．３問合せ処理７．２データベースの格納方式１．記憶装置とデータの格納 (a) ディスクのアクセス単位データベースは通常ディスクに格納される。【ディスクのアクセス単位】 ①ディスクは，シリンダ，トラック，セクタなどの単位に分割される。 ②データは、セクタの整数倍の大きさのページ（またはブロック）と呼ばれる単位でアクセスされる。【注意】用語については、機種またはOS依存なので、利用ハードウェア等のマニュアル等を参照。 (b) タプルの格納表のタプルは、DBMS内部では通常レコードと呼ばれる。【DBMS内部の呼び方】 ①レコード ②フィールド ③同一形式のレコードの集まり：フィールドの集まり：タプルの属性：ファイル (c) 固定長と可変長ということ固定長レコードと可変長レコード ①可変長レコードの方が複雑な格納方法 ②画像や音声データなど、サイズの大きな属性の場合、工夫が必要【例】画像ファイルを別に格納し、属性ではファイル名を指定する。 (d) ファイル内レコードの基本操作 ① ② ③ ④ 読込（read）追加（append）変更（update）削除（delete）ファイル全体では、 ⑤ オープン（Open） ⑥ クローズ（Close） (e) 格納方式（アクセス法）容量、検索や更新の効率に考慮して格納方式を決める。 ①ヒープ（heap: 積み重ねた山、堆積等の意味） ②索引編成（index access） ③B木（Balance Tree/Bush Tree：平衡木／潅木）最も単純なものが２分B木 ④ハッシング（Hashing: ごちゃまぜの意味）２．ヒープ（heap）・・・最も単純キー値とは無関係に発生順等によりファイル内に格納する。 ①ファイル内を順番に読んでいくので検索などの効率が悪い。 ②二次索引を付加して検索を効率化する工夫が行われる。 ③ 空き領域にレコード追加を行う。 ④ レコードの削除はページ内空き領域に戻すことで行う。３．索引編成（index access） (a) 構成の概要レコードは、キーの順序で整列して格納（キーの最大値を索引に用いているが、最小値でも良い）索引 007 015 データレコード 001 003 005 007 009 011 013 015 017 018 021 023 023 多量の索引を持つことができるよう、階層構造にする場合もある。 (b) 領域の管理 ① ある程度余裕を持った大きさにして、あらかじめ空き領域を設けておく。 ② オーバフロー領域と呼ばれる共通領域を設けておく。 ③ レコードの追加は、キー値により該当位置を決め、空き領域に書き込む。 ④ 該当位置に追加できなくなったら、オーバフロー領域に書き込む。 ⑤ キー以外のレコード変更は該当レコードを書き換える。 ⑥ キー値の変更は、一旦削除して追加する。 ⑦ 削除は、レコードを空き領域に戻す。 ⑧ レコード追加や削除が何回も続くと、ファイルアクセス効率が悪化するので、再編成を行う。 (c) 索引編成の特徴 ① 索引を用いるので高速になる。 ② キー値を一つ指定するだけでなく不等号で指定した検索も高速である。 ③ レコード追加や削除が頻繁に行われる場合、アクセス効率が悪化する。ただし、再編成で効率化できる。４．B木（Balance Tree） (a) 構成の概要 ① 高さが揃った木構造。 ② データは一番下の階層（葉ノード）に格納。 ③ データ追加や削除では、必要に応じて木構造を変更して高さの変更を保つ（アルゴリズムについては他の文献参照）。 ④ 葉ノードから次の葉ノードへのリンクによって順次アクセスが可能。 32 12 5 8 12 80 22 14 48 18 22 74 24 28 89 32 95 ・・・レコード・・・ (b) アクセス方法 ① ② ③ ④ ⑤ ⑥ キー値を指定した読み出しは、木のルートから索引をたどることで行う。不等号条件の場合、葉ノード間のリンクを用いて順次アクセスを行う。レコード追加は、キー値で位置を決める。葉ノードに空きがなければ、レコードを分割して木構造を変更する。削除時は該当レコードの削除で行う。該当葉ノードの空きが一定以上になると、ノードの統合を行う。 (c) B木の特徴 ① 中間部は索引部専用なので、１ページに多くのリンクを入れることができる。 ② 木の高さは通常３階層程度なので、高速な検索が可能。 ③ 木の構造を動的に変更することで、データ更新の頻度が多くても効率の良いアクセスができる。５．ハッシング（Hashing） (a) 方法の概要ハッシングと呼ばれる関数によってキー値をレコード位置に変換する。・・・直接編成法（Direct Access）のひとつ・・・キー値ハッシュ関数レコード位置格納レコード (b) ハッシング法さまざまな方法があるので、アルゴリズム関係の書籍で確認しておこう。（キー値によりランダムにかつバランスよく配置されるものがよい）・除算法・重合せ法・基数変換法・数字分解法 (c) ハッシング法のバラエティ ① レコード位置を直接求めるのではなく、レコード位置を記録した変換表内の位置を求める方法。 ② 格納するレコード数をあらかじめ指定する必要があるが、レコード数の増減に柔軟に対応する拡張可能ハッシング。キー値ハッシュ関数変換表アドレスレコード位置ファイルレコード (d) ハッシング法によるアクセス ① キー値をハッシングしてファイル内の位置を決めてレコードを読み込み、あるいは更新する。 ② レコード追加は、キー値をハッシングしてファイル内の位置を決めて行う。 ② キーが衝突したら、キー衝突のための処理を行う。 ③ 削除は、該当位置を空きとする。 (e) ハッシング法の特徴 ① キー値を指定したアクセス効率がよい。 ② 不等号等によるキー値の範囲指定アクセスの効率が悪い。 ③ 異なったハッシュ値が同じ値になる（衝突）ことがあるので対策が必要である（アルゴリズム関連の書籍参照）。