Day 8の物理的ファイル構造

適当なメモ。まさにちらしの裏。

レコードの位置決め法。スキャン(scan)、探索(search)、インデックス法(indexing)、ハッシュ法(hashing)とある。

レコード。タプル。表の横1行だったような。

スキャン。O(n)

探索。ソートされた中(順次ファイル)から探す。2分探索(binary search)はO(log2n)。ブロック探索はO(√n)。

インデックス法。最もポピュラー。2項ファイル(binary file)。本の索引のような感じ。
順序キー(ordering key)。順序フィールドがキーになっている場合。
順序フィールド。物理的に順次となっているフィールド。?
1次インデックス、2次インデックス。順序キー上か順序キー以外のフィールド上に定義されたインデックス。

多段インデックス。ISAM、B木、B+木など。
順序キーって何?

順序キー(ordering key)。順序フィールドがキーになっている場合。
順序フィールド。物理的に順次となっているフィールド。?

物理的に順次?
2項ファイルで順になってるフィールド?
1次インデックス=順序キー上。2次=順序キー以外。
2次インデックスの例。代表背番号がキー。キー?
スキャンの説明のとこ。

探索キー(search key)。キー(候補キー)を通常探索フィールド(search field)とし、これを探索キーと呼ぶ。

何だ、キーって。
「DB論の教科書ぉ」(ドラ)
P190
レコードのキーは、リレーションでいえば探索キー。
リレーション ←→ ファイル
タップル ←→ レコード
属性 ←→ フィールド

フィールドは、表の縦の1行、というか、縦1列っぽい。
ってことで、代表背番号が探すフィールド = 探索フィールド = 探索キー。
表はIDでソートされてる、ID順で並べられてる。代表背番号はばらばら、12、23、1、…。
これが2次インデックスの例ってことは、代表背番号は順序キーじゃない。2項ファイルは代表背番号でソートされてるので、順序キーってのは、実際の表で順になってるキー、この場合はID。
スクロールがめんどいので再。

順序キーって何?

順序キー(ordering key)。順序フィールドがキーになっている場合。
順序フィールド。物理的に順次となっているフィールド。?

物理的に順次?

ファイルの表の中でソートされてるフィールドが順序フィールド。順序フィールドで探す場合、それを順序キーと呼ぶ、と。
ん? 1次インデックスの場合は2項ファイル要るのか?

2次インデックス候補キー以外である場合。真ん中、うわっ「まんなか」で「╋」とか出てきた、真ん中の表がよくわからん。同じ値持ってるリスト、一覧、集合?

密集インデックス。インデックス=2項ファイル? インデックスに、順序フィールドの全ての値。これ必要?(↑) 2項ファイルの方が早いのかな。
点在インデックス。いくつかの値しか持たない。表のファイルの中の移動する感じ?

多段インデックス。ってこれ書いたような。

多段インデックス。ISAM、B木、B+木など。
順序キーって何?

順序キー、OK。
多段インデックス。インデックスを木で構成する。

ISAM。インデックスキーを順序キーとすることで、段数を1つ減らせる。
減らせる? わざわざファイルの表をソートしなきゃならなくね?
というか、順序キーとする、って、よくわからん。ファイルの中の順番になってるフィールドが順序キー、って方向なんじゃ?

ISAMインデックス。
あ、木が2項ファイルの代わりになるのか。あれ? 2項ファイルってどこで使うの?
pって何だ? どこにも出てきてないような。
挿入や削除で、動的な再構成は行われない。結果、非平衡木になる。

B+木。現在最も普及。
他の多段インデックスとの比較。

B+は平衡木。ISAMは非平衡木。

B+は探索キー上に定義。ISAMは順序キー。
あれ? ISAMはどうやって、探すんだ? 探索キー=順序キーの時だけ?

B+は中間ノードもデータポインタを持たない。B木は持つ。
データポインタ?

B+は同じ探索キー値が複数回現れることがある。B木は1度のみ。

B+は、中間ノードと葉ノードが似てて実装楽、削除も楽。
B+は、オーダを大きく取って、ノード数を減らせる。結果時間減。
オーダって?

ってか、B木の説明がないんですが。
おわり。

結果、わかったこと。相原氏はサッカー好きである。
いやそれはだいぶまえから。