データベースインデックス

Question

分散環境で使用するためのデータベースインデックスの「素朴な」実装を開発する必要があります。私は主題についてほとんど何も知らないし、時間が少しだけ圧迫されている。

私は、このテーマに関するいくつかの意見、例、アルゴリズムを聴きたいと思います。 私は実装が必要なものを精神的に表現したいと思っています。

EDIT：は、私は、クラスタ化インデックス

を参照しています

Answer 1

あり、インデックスの基本的に2つの主な種類があります：

• クラスタ化された（つまり、データが物理的に整理し、あなたが再ソートはそれ

  一般的な使用例：物理的な構成は通常挿入順序と同じであるため、再ソートのオーバーヘッドは問題にはなりません。たとえば、シーケンシャルUID（データベースコンテキストでは「IDENTITY」フィールドと呼ばれる）の場合です。

  クラスタ化インデックス作成の明らかな欠点は、データにこのようなインデックスを1つだけ設定できることです。

  挿入順がまさにソート順である場合はナイーブ実装です。リストを使用します。

  1. 挿入はOである（1）：あなただけのアクセスはO（1）のIDのがシーケンシャルであれば（すなわち、配列のインデックスが正確にUIDと一致する）、O（ログ）そうです、リスト
  2. の新しいデータを追加します

• クラスタ化されていない（つまり、あなたはハッシュテーブルのように、データ上のポインタを保持する）

  典型的なユースケース：それは大きな挿入オーバーヘッドに誘導するためのクラスタリングが適切ではありません。

必要に応じて、あなたはおそらく、インデックス関連情報の広範なリポジトリはhere

Answer 2

A本当に速い-と-イージー利用可能であるこれら二つのデータ構造

に使用してしまいますネイティブのassociative arrayフォーマットを持つ言語に最も適した、本当に素朴なインデックスの実装は、インデックスを作成しているカラムの現存値であり、その値がその値を持つ行の行IDの配列であるハッシュです。