第７章　データベース管理システム ７．１ データベース管理システムの概要 ７．２ データベースの格納方式 ７．３ 問合せ処理

７．２ データベースの格納方式 １．記憶装置とデータの格納 (a) ディスクのアクセス単位 データベースは通常ディスクに格納される。 【ディスクのアクセス単位】 ①ディスクは，シリンダ，トラック，セクタなどの単位に分割される。 ②データは、セクタの整数倍の大きさのページ（またはブロック）と呼ばれる単位でアクセスされる。 【注意】 用語については、機種またはOS依存なので、 利用ハードウェア等のマニュアル等を参照。

表のタプルは、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 001 003 005 007 009 011 013 015 015 017 018 021 023 023 多量の索引を持つことができるよう、階層構造にする場合もある。

(b) 領域の管理 ① ある程度余裕を持った大きさにして、あらかじめ空き領域を設けておく。 ② オーバフロー領域と呼ばれる共通領域を設けておく。 ③ レコードの追加は、キー値により該当位置を決め、空き領域に書き込む。 ④ 該当位置に追加できなくなったら、オーバフロー領域に書き込む。 ⑤ キー以外のレコード変更は該当レコードを書き換える。 ⑥ キー値の変更は、一旦削除して追加する。 ⑦ 削除は、レコードを空き領域に戻す。 ⑧ レコード追加や削除が何回も続くと、ファイルアクセス効率が悪化するので、再編成を行う。

(c) 索引編成の特徴 ① 索引を用いるので高速になる。 ② キー値を一つ指定するだけでなく不等号で指定した検索も高速である。 ③ レコード追加や削除が頻繁に行われる場合、アクセス効率が悪化する。ただし、再編成で効率化できる。

４．B木（Balance Tree） (a) 構成の概要 ① 高さが揃った木構造。 ② データは一番下の階層（葉ノード）に格納。 ③ データ追加や削除では、必要に応じて木構造を変更して高さの変更を保つ（アルゴリズムについては他の文献参照）。 ④ 葉ノードから次の葉ノードへのリンクによって順次アクセスが可能。 32 80 12 22 48 74 89 95 5 8 12 14 18 22 24 28 32 ・・・　レコード　・・・

(b) アクセス方法 キー値を指定した読み出しは、木のルートから索引をたどることで行う。 不等号条件の場合、葉ノード間のリンクを用いて順次アクセスを行う。 レコード追加は、キー値で位置を決める。 葉ノードに空きがなければ、レコードを分割して木構造を変更する。 削除時は該当レコードの削除で行う。 該当葉ノードの空きが一定以上になると、ノードの統合を行う。

(c) B木の特徴 中間部は索引部専用なので、１ページに多くのリンクを入れることができる。 木の高さは通常３階層程度なので、高速な検索が可能。 木の構造を動的に変更することで、データ更新の頻度が多くても効率の良いアクセスができる。

５．ハッシング（Hashing） (a) 方法の概要 ハッシングと呼ばれる関数によってキー値をレコード位置に変換する。 ・・・直接編成法（Direct Access）のひとつ・・・ キー値 ハッシュ関数 レコード位置 格納レコード

アルゴリズム関係の書籍で確認しておこう。 (b) ハッシング法 さまざまな方法があるので、 アルゴリズム関係の書籍で確認しておこう。 （キー値によりランダムにかつバランスよく配置されるものがよい） ・除算法 ・重合せ法 ・基数変換法 ・数字分解法

(c) ハッシング法のバラエティ ① レコード位置を直接求めるのではなく、レコード位置を記録した変換表内の位置を求める方法。 ② 格納するレコード数をあらかじめ指定する必要があるが、レコード数の増減に柔軟に対応する拡張可能ハッシング。 キー値 ハッシュ関数 レコード位置 ファイル 変換表 アドレス レコード

(d) ハッシング法によるアクセス キー値をハッシングしてファイル内の位置を決めてレコードを読み込み、あるいは更新する。 レコード追加は、キー値をハッシングしてファイル内の位置を決めて行う。 キーが衝突したら、キー衝突のための処理を行う。 削除は、該当位置を空きとする。

(e) ハッシング法の特徴 ① キー値を指定したアクセス効率がよい。 ② 不等号等によるキー値の範囲指定アクセスの効率が悪い。 ③ 異なったハッシュ値が同じ値になる（衝突）ことがあるので対策が必要である（アルゴリズム関連の書籍参照）。