インデックスタイプの概要Oracle、MySQL、PostgreSQL、MS SQL
コメントの1つで、インデックスについて詳しく説明するリクエストがありましたが、RunetにはさまざまなDBMSのサポートされているインデックスの概要データが実質的にないため、このレビューでは、最も一般的なDBMSでサポートされているインデックスのタイプを検討します
Bツリーインデックスファミリは、最も一般的に使用されるタイプのインデックスで、順序付けられたキーのバランスの取れたツリーとして編成されます。 それらは、リレーショナルおよび非リレーショナルのほぼすべてのDBMSで、ほぼすべての種類のデータでサポートされています。
ほとんどの場合それらをよく知っている（または、たとえばここで読むことができる）ので、おそらくここで注意すべき唯一のことは、このタイプのインデックスは、値の分布がよくハイパワー（カーディナリティ）のセットに最適であることです-一意の値の数）。
現時点では、すべてのDBMSデータには、それらを操作するための空間データ型と機能があります。Oracleの場合は、MDSYSスキーマのタイプと関数のセットです。PostgreSQLの場合は、MySQLのポイント、ライン、lseg、ポリゴン、ボックス、パス、ポリゴン、円-ジオメトリ、ポイント、ラインストリング、ポリゴン、マルチポイント、マルチラインストリング、マルチポリゴン、geometrycollection、MS SQL-ポイント、マルチポイント、ラインストリング、マルチラインストリング、ポリゴン、マルチポリゴン、GeometryCollection。
空間クエリ操作スキームでは、通常2段階または2段階のフィルタリングが区別されます。 空間サポートが不十分なDBMSは、最初の段階（粗フィルタリング、MySQL）でのみ機能します。 原則として、オブジェクトの近似、近似表現がこの段階で使用されます。 最も一般的なタイプの近似は、最小境界矩形[MBR] [100]です。
空間データタイプには、Rツリー（Rツリーインデックス）とグリッド（グリッドベースの空間インデックス）に基づく特別なインデックス方法があります。
空間グリッドインデックスは、Bツリーに似たツリー構造ですが、空間データへのアクセスを整理するために使用されます。たとえば、2次元座標（緯度と経度）を持つ地理データなどの多次元情報にインデックスを付けるために使用されます。 ） この構造では、ツリーのノードは空間のセルです。 たとえば、2次元空間の場合：最初に、親領域全体が厳密に定義された解像度グリッドに分割され、次に、オブジェクトの数がセル内のオブジェクトの設定最大値を超える各グリッドセルが次のレベルのサブグリッドに分割されます。 このプロセスは、最大のネスティングが達成されるまで（インストールされている場合）、またはすべてがオブジェクトの最大数を超えないセルに分割されるまで続きます。
3次元または多次元空間の場合、これらは直方体（直方体）または平行六面体になります。
クアッドツリーはグリッドベースの空間インデックスのサブセットであり、親セルには常に4つの子があり、グリッドの解像度はデータの性質または複雑さによって異なります。
R-Tree（Regions Tree）も、1984年にAntonin Guttmanによって提案されたSpatial Gridに似たツリーのようなデータ構造です。 このデータ構造は、スペースを多くの階層的にネストされたセルに分割しますが、空間グリッドとは異なり、親セルを完全にカバーする必要はなく、交差する場合があります。
さまざまなアルゴリズムを使用して、オーバーフローした頂点を分割できます。これにより、Rツリーがサブタイプに分割されます：二次および線形の複雑度（もちろん、Guttmanは指数関数的複雑度で説明されています-完全検索ですが、もちろん、彼はどこでも使用されていません）
二次サブタイプは、すべてのオブジェクトをカバーする最小領域を持つ2つの長方形に分割されます。 線形-最大距離で除算されます。
ハッシュインデックスはArthur Fullerによって提案され、値自体を保存するのではなく、ハッシュを使用して、大きなフィールドのインデックスのサイズを縮小します（したがって、処理速度が向上します）。 したがって、HASHインデックスを使用してクエリを実行する場合、フィールド値から検索されたものではなく、求められた値からのハッシュとフィールドハッシュが比較されます。
ハッシュ関数は非線形であるため、このインデックスは値で並べ替えることができません。これにより、使用量を増やしたり減らしたりすることができなくなり、比較ではnullになります。 さらに、ハッシュは一意ではないため、ハッシュの一致には衝突解決方法が使用されます。
ビットマップインデックス-ビットインデックスの方法は、可能な列値ごとに個別のビットマップ（0と1のシーケンス）を作成します。各ビットはインデックス値を持つ行に対応し、その値が1の場合、ビット位置に対応するレコードにはインデックス値が含まれますこの列またはプロパティ。
ビットマップ
ビットインデックスの主な利点は、低消費電力で値によるクラスタリングが良好な大規模なセットでは、インデックスがB * -treeより小さいことです。 （詳細はこちらまたはこちらをご覧ください ）
逆索引もBツリー索引ですが、逆キーを使用します。主にOLTPシステムで単調増加する値（たとえば、自動増分識別子）に使用され、索引の最後の葉ブロックの競合を排除します。 値を反転することにより、2つの隣接するインデックスエントリが異なるインデックスブロックに分類されます。 範囲検索には使用できません。
例：
ご覧のとおり、インデックスの値はテーブル自体の値よりもはるかに大きく変化するため、bツリー構造では、それらは異なるブロックに分類されます。
インバーテッドインデックスは、特定のキーを含むテーブルエントリのアドレスのソートされたリストをキートークンごとに格納するフルテキストインデックスです。
簡略化された形式では、次のようになります。
部分インデックスは、インデックス自体の特定の条件を満たすテーブルの一部に構築されるインデックスです。 このインデックスは、インデックスのサイズを縮小するために作成されました。
最も柔軟なタイプのインデックスは機能インデックスです。つまり、キーにユーザー定義関数の結果が格納されるインデックスです。 関数インデックスは、SQLコマンドで比較される前に値が前処理されるフィールド用に作成されることがよくあります。 たとえば、大文字と小文字を区別せずに文字列データを比較する場合、UPPER関数がよく使用されます。 UPPER関数を使用して関数インデックスを作成すると、このような比較の有効性が向上します。
さらに、機能インデックスは、特定のDBMSに他の欠落しているタイプのインデックスを実装するのに役立ちます（おそらく、Hash for Oracleなどのビットインデックスを除く）
PostgreSQLでは、GiSTを使用すると、ネイティブデータ型のR-Treeに基づいてインデックスを作成できます。 これを行うには、Rツリーメカニズムの7つの機能すべてを実装する必要があります。
さらに、ここで読むことができます：
Oracle Spatialユーザーズ・ガイドおよびリファレンス
MS SQLの空間データ
MS SQL：空間インデックス作成の概要
ヒルベルトrツリー
PostgreSQLの空間タイプ
PostgreSQL空間関数
Microsoft SQL Server 2000の空間データのインデックス作成
パパディアスD.、テオドリディスT.空間関係、最小境界長方形および空間データ構造//テクニカルレポートKDB-SLAB-TR-94-04、
Faloutsos C.、Kamel I. Hilbert R-Tree：フラクタルを使用したRツリーの改善//メリーランド大学CS学科、TechnicalResearch Report TR-93-19、
ウィキペディア：ヒルベルトRツリー
外部メモリの検索方法
アーサー・フラー。 ハッシュキーを使用したインテリジェントなデータベース設計
PS。 おそらく、何か言及したり、PMに書いたり、コメントに入れたりするのを忘れたのかもしれません。
Bツリー
Bツリーインデックスファミリは、最も一般的に使用されるタイプのインデックスで、順序付けられたキーのバランスの取れたツリーとして編成されます。 それらは、リレーショナルおよび非リレーショナルのほぼすべてのDBMSで、ほぼすべての種類のデータでサポートされています。
ほとんどの場合それらをよく知っている（または、たとえばここで読むことができる）ので、おそらくここで注意すべき唯一のことは、このタイプのインデックスは、値の分布がよくハイパワー（カーディナリティ）のセットに最適であることです-一意の値の数）。
空間インデックス
現時点では、すべてのDBMSデータには、それらを操作するための空間データ型と機能があります。Oracleの場合は、MDSYSスキーマのタイプと関数のセットです。PostgreSQLの場合は、MySQLのポイント、ライン、lseg、ポリゴン、ボックス、パス、ポリゴン、円-ジオメトリ、ポイント、ラインストリング、ポリゴン、マルチポイント、マルチラインストリング、マルチポリゴン、geometrycollection、MS SQL-ポイント、マルチポイント、ラインストリング、マルチラインストリング、ポリゴン、マルチポリゴン、GeometryCollection。
空間クエリ操作スキームでは、通常2段階または2段階のフィルタリングが区別されます。 空間サポートが不十分なDBMSは、最初の段階（粗フィルタリング、MySQL）でのみ機能します。 原則として、オブジェクトの近似、近似表現がこの段階で使用されます。 最も一般的なタイプの近似は、最小境界矩形[MBR] [100]です。
空間データタイプには、Rツリー（Rツリーインデックス）とグリッド（グリッドベースの空間インデックス）に基づく特別なインデックス方法があります。
空間グリッド
空間グリッドインデックスは、Bツリーに似たツリー構造ですが、空間データへのアクセスを整理するために使用されます。たとえば、2次元座標（緯度と経度）を持つ地理データなどの多次元情報にインデックスを付けるために使用されます。 ） この構造では、ツリーのノードは空間のセルです。 たとえば、2次元空間の場合：最初に、親領域全体が厳密に定義された解像度グリッドに分割され、次に、オブジェクトの数がセル内のオブジェクトの設定最大値を超える各グリッドセルが次のレベルのサブグリッドに分割されます。 このプロセスは、最大のネスティングが達成されるまで（インストールされている場合）、またはすべてがオブジェクトの最大数を超えないセルに分割されるまで続きます。
3次元または多次元空間の場合、これらは直方体（直方体）または平行六面体になります。
クワッドツリー
クアッドツリーはグリッドベースの空間インデックスのサブセットであり、親セルには常に4つの子があり、グリッドの解像度はデータの性質または複雑さによって異なります。
Rツリー
R-Tree（Regions Tree）も、1984年にAntonin Guttmanによって提案されたSpatial Gridに似たツリーのようなデータ構造です。 このデータ構造は、スペースを多くの階層的にネストされたセルに分割しますが、空間グリッドとは異なり、親セルを完全にカバーする必要はなく、交差する場合があります。
さまざまなアルゴリズムを使用して、オーバーフローした頂点を分割できます。これにより、Rツリーがサブタイプに分割されます：二次および線形の複雑度（もちろん、Guttmanは指数関数的複雑度で説明されています-完全検索ですが、もちろん、彼はどこでも使用されていません）
二次サブタイプは、すべてのオブジェクトをカバーする最小領域を持つ2つの長方形に分割されます。 線形-最大距離で除算されます。
ハッシュ
ハッシュインデックスはArthur Fullerによって提案され、値自体を保存するのではなく、ハッシュを使用して、大きなフィールドのインデックスのサイズを縮小します（したがって、処理速度が向上します）。 したがって、HASHインデックスを使用してクエリを実行する場合、フィールド値から検索されたものではなく、求められた値からのハッシュとフィールドハッシュが比較されます。
ハッシュ関数は非線形であるため、このインデックスは値で並べ替えることができません。これにより、使用量を増やしたり減らしたりすることができなくなり、比較ではnullになります。 さらに、ハッシュは一意ではないため、ハッシュの一致には衝突解決方法が使用されます。
ビットマップ
ビットマップインデックス-ビットインデックスの方法は、可能な列値ごとに個別のビットマップ（0と1のシーケンス）を作成します。各ビットはインデックス値を持つ行に対応し、その値が1の場合、ビット位置に対応するレコードにはインデックス値が含まれますこの列またはプロパティ。
| EmpID | 性別 |
|---|---|
| 1 | 男性 |
| 2 | 雌 |
| 3 | 雌 |
| 4 | 男性 |
| 5 | 雌 |
ビットマップ
| 価値 | 開始する | 終わり | ビットマスク |
|---|---|---|---|
| 男性 | 最初の行アドレス | 最終行アドレス | 10010 |
| 雌 | 最初の行アドレス | 最終行アドレス | 01101 |
ビットインデックスの主な利点は、低消費電力で値によるクラスタリングが良好な大規模なセットでは、インデックスがB * -treeより小さいことです。 （詳細はこちらまたはこちらをご覧ください ）
逆インデックス
逆索引もBツリー索引ですが、逆キーを使用します。主にOLTPシステムで単調増加する値（たとえば、自動増分識別子）に使用され、索引の最後の葉ブロックの競合を排除します。 値を反転することにより、2つの隣接するインデックスエントリが異なるインデックスブロックに分類されます。 範囲検索には使用できません。
例：
| テーブル内のフィールド（ビン） | 逆索引キー（ビン） |
|---|---|
| 00000001 | 10,000,000 |
| ... | ... |
| 00001001 | 10010000 |
| 00001010 | 01010000 |
| 00001011 | 11010000 |
反転インデックス
インバーテッドインデックスは、特定のキーを含むテーブルエントリのアドレスのソートされたリストをキートークンごとに格納するフルテキストインデックスです。
| 1 | ママはフレームを洗いました |
| 2 | お父さんはフレームを洗いました |
| 3 | お父さんは車を洗った |
| 4 | ママは車を磨いた |
簡略化された形式では、次のようになります。
| お母さん | 1.4 |
| 石鹸 | 1 |
| ラム | 1,2 |
| お父さん | 2,3 |
| ポリッシュ | 4 |
| 車 | 3.4 |
部分インデックス
部分インデックスは、インデックス自体の特定の条件を満たすテーブルの一部に構築されるインデックスです。 このインデックスは、インデックスのサイズを縮小するために作成されました。
関数ベースのインデックス
最も柔軟なタイプのインデックスは機能インデックスです。つまり、キーにユーザー定義関数の結果が格納されるインデックスです。 関数インデックスは、SQLコマンドで比較される前に値が前処理されるフィールド用に作成されることがよくあります。 たとえば、大文字と小文字を区別せずに文字列データを比較する場合、UPPER関数がよく使用されます。 UPPER関数を使用して関数インデックスを作成すると、このような比較の有効性が向上します。
さらに、機能インデックスは、特定のDBMSに他の欠落しているタイプのインデックスを実装するのに役立ちます（おそらく、Hash for Oracleなどのビットインデックスを除く）
インデックスタイプの概要表
| MySQL | PostgreSQL | MS SQL | オラクル | |
| Bツリーインデックス | あります | あります | あります | あります |
| サポートされている空間インデックス | 二次Rツリー | Rtree_GiST（線形分割を使用） | 4レベルのグリッドベースの空間インデックス（地理データと測地データは分離） | 二次パーティションを持つRツリー。 クワッドツリー |
| ハッシュインデックス | メモリなどのテーブルのみ | あります | いや | いや |
| ビットマップインデックス | いや | あります | いや | あります |
| 逆インデックス | いや | いや | いや | あります |
| 反転インデックス | あります | あります | あります | あります |
| 部分インデックス | いや | あります | あります | いや |
| 関数ベースのインデックス | いや | あります | あります | あります |
PostgreSQLでは、GiSTを使用すると、ネイティブデータ型のR-Treeに基づいてインデックスを作成できます。 これを行うには、Rツリーメカニズムの7つの機能すべてを実装する必要があります。
さらに、ここで読むことができます：
Oracle Spatialユーザーズ・ガイドおよびリファレンス
MS SQLの空間データ
MS SQL：空間インデックス作成の概要
ヒルベルトrツリー
PostgreSQLの空間タイプ
PostgreSQL空間関数
Microsoft SQL Server 2000の空間データのインデックス作成
パパディアスD.、テオドリディスT.空間関係、最小境界長方形および空間データ構造//テクニカルレポートKDB-SLAB-TR-94-04、
Faloutsos C.、Kamel I. Hilbert R-Tree：フラクタルを使用したRツリーの改善//メリーランド大学CS学科、TechnicalResearch Report TR-93-19、
ウィキペディア：ヒルベルトRツリー
外部メモリの検索方法
アーサー・フラー。 ハッシュキーを使用したインテリジェントなデータベース設計
PS。 おそらく、何か言及したり、PMに書いたり、コメントに入れたりするのを忘れたのかもしれません。
All Articles