データ格納方法：不揮発性記憶媒体、ページ、レコード、索引

大学の期末試験のために書いたものです。間違い等は悪しからず。

データの格納

３層スキーマ

データベースにおけるスキーマとはデータの構造、性質や他のデータとの関連、データベースを操作する時のルールや表現法などを定義したもののことです。

(http://db-study.com/archives/36)

この設計図を元に、３層スキーマを構成。

スキーマ名	説明
外部スキーマ	概念スキーマで定義された論理データから必要なデータを取り出したもの。(ビューなどに相当)
概念スキーマ	DB上の論理データ。DBに保持するデータの要素およびデータ同士の関係を定義する。(テーブルに相当)
内部スキーマ	概念スキーマで定義された論理データを具体的にどのようにDBMS内部に格納するかを定義する。

この内部スキーマが、DBシステムに依存して変化する。

記憶素子

揮発性と不揮発性

揮発性: 電源を供給しないとデータを保存できない
不揮発性: 電源を供給し続けなくてもデータを保持可能
- Flash Memory, FeRAM（強誘電体メモリ）
- MRAM, PRAM（相変化メモリ）-> SCM（Storage Class Memory）

磁気ディスク

磁気ディスク（じきディスク）とは、データ記録に磁性体を塗布した円盤を回転させて行う記録媒体（ディスクメディア・電子媒体→磁気記録）の名称である（wikiより）

不揮発性で記憶容量が大きい
bit単価が低い
磁気テープに比べて性能面で優れる

一般的なディスクの特性とその構成要素

回転速度：3000 ~ 15000 rpm
シーク時間：0.7ms（隣接）~ 20ms（最内 ⇆ 最外）
セクタのサイズ：512B
ディスクのサイズ：3.5, 2.5, 1 inch
シリンダ数：6000 ~ 10000
ディスク枚数：1 ~ 9

ページへの格納

最初に，データベースを構成するファイルについて簡単に触れておきましょう。データベースは大きく分けて，「データ・ファイル」「ログ・ファイル」「コントロール・ファイル（ルート・ファイル）」の3種類のファイルで構成されます。（https://tech.nikkeibp.co.jp/it/article/COLUMN/20060113/227231/ より）

ページはデータ・ファイルの基本単位。通常は4KB[8セクタ]程度。これが論理的なアクセスの固まりになる。

ページ内のアクセス

スロット番号からオフセットを得る。
- 相対レコード番号：Tuple ID(TID) = #Page + #Slot
ページ内の有効活用
- ヘッダ情報とデータを逆から詰める
レコードにはスロット番号でアクセスする。このときページの先頭にはレコードのスロットのアドレスを格納するヘッダが含まれる。

レコードの構成

固定長フィールドと可変長フィールドに分けられる。このとき属性の位置と物理的な位置は独立であり、固定長フィールドの情報（個数・長さ）は別に持つ。

索引（インデックス）

内容からTIDを示すこと。

インデックスは「探すレコードを識別するデータの項目」「対象レコードの格納位置を示すポインタ」で構成されており、これを利用してデータの格納位置を特定し、その位置を直接アクセスする事で、表の検索速度を上げることができます。(https://www.atmarkit.co.jp/ait/articles/1703/01/news199.html より)

索引構造

検索の条件により必要な索引構造は異なるため、異なる構造を持つ複数の索引を提供するデータベース製品も存在する。

転置インデックス

転置インデックス（てんちインデックス、Inverted index）とは、全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造をいう。転置索引、転置ファイル、逆引き索引などとも呼ばれる。(wikiより)

転置ファイルを用いて、属性の値からPageとSlotを指し示す。

B木

現在のほとんどの索引はB木を採用している。

B木の条件
- どのノードの子の個数も$k+1$個以上(ただし根と葉はこの限りではない）
- どのノードの個の個数もたかだか$2k+1$個以下
- 根は$2$以上の子を持つ（ただし根自身が葉である場合はこの限りではない）
- 根から葉に至る経路の長さは、どの葉も同じである

B木を索引に用いるとき、各ノードがページに対応する。また１ページには、$k$レコードないし$2k$レコードが含まれ、利用効率が半分以下にならないようにする。この条件を満たすために以下を行う。

子ノードが$2k$個を越えるとノードを分割し、中間の値をノードに格納
親のノードも再帰的に同じ処理をして、根までいくと高さが増える

<参考>
https://www.atmarkit.co.jp/fcoding/articles/delphi/05/delphi05a.html

B*木

ノードの分割時、自分自身だけでなく兄弟のノードも見る
兄弟がいっぱいになったら、親と2ノードの分（$4k+2$)を3ノードと2つの親に配る
各ノードは$4k/3$のレコードを含むから、効率は2/3以上

B+木

実際のデータベースでは隣接するデータベースを連続して参照することが往往にしてあるので、挿入コストを犠牲に葉ノードを連結。

データの順アクセスが可能なように改良
- レコードは葉ノードのみに格納
- 葉ノードの間をリンクで結合

<参考>
https://ja.wikipedia.org/wiki/B%2B%E6%9C%A8

ハッシング（Hashing）

ハッシュ関数に基づく索引は、一般にB木よりも性能面およびサイズ面で有利であるが、範囲検索はできず、完全一致検索にのみ利用できる。

格納時と検索時に同じハッシュ関数を用いることで、アクセス先を特定
- ハッシュ表をつくり、TID等の情報を格納
- 衝突（Hash Collision）が発生しない限りは、検索コストは$O(c)$
- 衝突への対処が必要
  - リストでTIDを繋げる
  - 空いているハッシュエントリーを使う
  - bitmapを使う -> カーディナリティが低い場合に最適
  - 拡張ハッシュ

<参考>
https://thinkit.co.jp/article/159/3

拡張ハッシュ

ハッシュ表のサイズを動的に変化させることで、衝突を防ぐ。

2の冪乗で変化：bit数に対応しているため
Depth：ハッシュ値の何bit目を見るか
拡張する過程でのコピーのコストが大きい

スーパーインポーズドコード

キーワードとシグネチャを対応
問い合わせにはシグネチャに演算を施したシグネチャを使用

以下に例を示す。

キーワード	シグネチャ
渋谷区	01001000
新宿区	00000101

このとき、「渋谷区 AND 新宿区」を表すシグネチャは001001101となる。少なくとの条件を満足するものが検索結果に含まれることが保証される。

<参考>
https://ci.nii.ac.jp/naid/110004833154

参考

http://db-study.com/archives/36
https://tech.nikkeibp.co.jp/it/article/COLUMN/20060113/227231/
https://www.atmarkit.co.jp/ait/articles/1703/01/news199.html
https://ja.wikipedia.org/wiki/%E8%BB%A2%E7%BD%AE%E3%82%A4%E3%83%B3%E3%83%87%E3%83%83%E3%82%AF%E3%82%B9
https://ja.wikipedia.org/wiki/%E7%B4%A2%E5%BC%95_(%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9)
https://www.atmarkit.co.jp/fcoding/articles/delphi/05/delphi05a.html
https://ci.nii.ac.jp/naid/110004833154