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

Question

分散環境で使用するデータベースインデックスの「ナイーブな」実装を開発する必要があります。私はその主題についてほとんど何も知りません、そして私は時間によって少しプレッシャーを感じています。

このテーマに関するいくつかの意見、例、アルゴリズムを聞きたいです。実装する必要があるものを精神的に表現できるようにしたいと思います。

編集：私はクラスター化インデックスを参照しています

Answer 1

インデックスには基本的に2つのタイプがあります。

• クラスター化（つまり、データは物理的に整理されており、必要に応じて挿入のたびに再ソートします）

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

  クラスタ化インデックスの明らかな欠点は、データにそのようなインデックスを1つしか持てないことです。

  挿入順序が正確に並べ替え順序である場合の単純な実装：リストを使用します。

  1. 挿入はO（1）です：リストの新しいデータを追加するだけです
  2. IDがシーケンシャル（つまり、配列インデックスがUIDと完全に一致する）の場合、アクセスはO（1）であり、それ以外の場合はO（log）です。

• 非クラスター化（つまり、ハッシュテーブルのようにデータにポインターを保持します）

  典型的な使用例：クラスタリングは、挿入のオーバーヘッドを大きくするため、適切ではありません。

ニーズに応じて、これら2つのデータ構造を使用することになります。

インデックス関連情報の広範なリポジトリは、こちらから入手できます。

Answer 2

ネイティブの連想配列形式を持つ言語に最も適した、非常に高速で簡単に実装できる、非常に単純なインデックス実装は、キーがインデックス付けする列の既存の値であり、値が配列であるハッシュです。その値を持つ行の行 ID の。