インデックス・格納方式と性能

結論：このレッスンの地図

DBの性能の話は、どう探すか（インデックス）、どう結合するか（結合方式）、**どう保つか（再編成）**の3つに分かれます。

インデックスの目的：本の索引と同じ

インデックス（索引）は、列の値から「そのデータがどこに格納されているか」へ直接たどるための仕組みです。目的は検索速度の向上で、全件を先頭から読む（全件走査）のを避けます。本の巻末索引で「正規化 → p.120」と引けば、全ページをめくらずに済むのと同じです。

検索のたびに全レコードを読んでいて遅いなら、検索条件に使っている列にインデックスを追加するのが最も効く対策です。領域を広げても、DBMSを入れ直しても、読む件数は減らないので速くなりません。

代わりに、データを追加・更新・削除するたびにインデックスも更新されるので、更新処理は少し重くなり、格納領域も増えます。

B木・B+木：深さがそろった木

B木は、1つのノード（節）が多くの子を持つ木（多分木）で、すべての葉が同じ深さになるように、ノードの分割と併合を行う平衡木です。データが偏って増えても木が片側だけ深くならないので、どのキーを探してもかかる手間がほぼ同じになります。

B+木はB木の改良版で、データ（またはデータへの位置）を葉にだけ持ち、葉どうしを順につないでいます。そのため、1件を探すときは根から葉へ下り、範囲で探すときは葉を横にたどります。

1件を探すときのノードのアクセス回数は木の深さと同じで、データ件数Xに対して log X のオーダ（件数が10倍になっても回数は少し増えるだけ）です。全件走査は X のオーダです。

ハッシュインデックスとB+木の使い分け

ハッシュインデックスは、キー値をハッシュ関数（値を決まった計算で番地に変える関数）に入れて格納位置を求めます。「＝」で1つの値を探す等価検索に最も強いです。

一方、ハッシュ値は元の値の大小や並び順を保たないので、「1万円以上」「今月」のような範囲検索や、「'DB'で始まる」のような前方一致検索には使えません。これらは値が順に並んでいるB+木が向いています。

ハッシュの衝突と理想の分布（一様分布）

ハッシュ関数は、異なるキー値を同じ格納位置に変換してしまうことがあります。これを衝突（コリジョン）といい、衝突したキーどうしをシノニム（同義語）と呼びます。4つのインデックス方式のうち、キー値から格納位置を計算するのはハッシュだけなので、衝突が起こりうるのもハッシュだけです。

衝突を減らすには、ハッシュ値が全番地に偏りなく散らばることが大切です。理想は一様分布（どの値も同じ確率で出る分布）で、このとき同じハッシュ値になる確率が最も低くなります。

下駄箱にたとえると、100人分の靴を100個の箱に入れるとき、誰がどの箱になるかが均等なら、1つの箱に何足も押し込まれにくくなります。正規分布・ポアソン分布・二項分布・幾何分布は、どれも特定の値に出やすさが集まる分布なので、ハッシュ値の理想にはなりません。

キー値をハッシュで番地に変えてレコードを置くファイルを直接編成ファイルといいます。ここでもハッシュ値の理想は一様分布です。

表の結合方式：主に4つあり、ソートマージは「並べ替えて突き合わせ」

RDBMSが2つの表を結合する方法は、主に4つあります。試験では「どの説明がソートマージ結合か」を問われます。

ソートマージ結合は、両方の表を結合する列の値で並べ替え、2つの表の先頭から順に突き合わせて結合します。名簿を2冊とも五十音順に並べてから、上から同時に見比べるやり方です。

データベース再編成：散らかった倉庫の片付け

データの追加・更新・削除を繰り返すと、削除後の空き領域が点在したり、収まりきらないデータがあふれ領域に飛ばされたりして、データの物理的な並びが乱れます。その結果、同じ検索でも読む場所が増え、アクセス効率が落ちます。

再編成は、データをいったん取り出して（アンロード）、詰め直して格納し直す（リロード）処理です。空き領域や乱れを解消し、アクセス効率を回復するために定期的に行います。