10

CHECKSUM 列タイプを使用して人為的にハッシュ インデックスを作成する場合、ルックアップは実際には O(1) ですか、それともクラスター化インデックスの場合のように O(lg n) ですか? ID 列に基づいて選択するテーブルがあり、ルックアップをできるだけ高速にする必要があります。クラスター化インデックスは最速のオプションですか? O(1) パフォーマンスを提供するものを探しています。

4

4 に答える 4

12

よし、2点。
SQL CHECKSUM 関数はハッシュ値を生成しません。実際に CRC 値を計算します。比較的多数の衝突が発生するため、ハッシュ チェックのベースにするのはあまり良い候補ではありません。ハッシュ関数が必要な場合は、hash_bytes 関数を確認する必要があります。
次に、実際にはハッシュ インデックスを作成していません。ハッシュ値に通常の B ツリーを作成しているため、ルックアップ時間は、同様のサイズのデータ​​型の他の B ツリー インデックスとまったく同じになります。
長い varchar 値の CRC またはハッシュを使用して、より少ないバイト数の比較を可能にすることで、パフォーマンスが少し向上する可能性がありますが、文字列比較は、必要な数のバイトしかチェックしません。一致しない最初の文字。ハッシュ値で一致する場合は、とにかく実際の値を再確認する必要があります。そのため、非常によく似た文字列がたくさんない限り、ハッシュ (または CRC) を使用してさらに多くのバイトを比較することになるでしょう。

要するに、これは賢明な計画ではないと思いますが、すべての最適化と同様に、特定のケースでテストしてから決定する必要があります。投稿していただける場合は、結果をご覧いただければ幸いです。また、クラスター化インデックスを使用する以外に、SQL サーバーで行をすばやく見つける方法はないと思います。

気になる場合は、Ingres (by CA) でハッシュ インデックスを作成して、O(1) を実現できます。真のハッシュ インデックスをサポートする他の RDBM も存在する可能性があります。

于 2008-11-26T22:52:53.103 に答える
6

SQLサーバーがネイティブにハッシュテーブルベースのインデックスを持っているとは思いません。BOLのドキュメントでは、計算値に基づいて標準（ツリー）インデックスを作成することについて説明しています。これは、一部のDBMSプラットフォームで使用できるインデックス構造である線形ハッシュテーブルと同じではありませんが、SQL Server（AFAIK）では使用できません。

このブログ投稿で説明されている手法を使用して、URLなどの大きな文字列値をハッシュして検索を高速化することで、ある程度のメリットが得られる場合があります。ただし、基になるインデックスは依然としてツリー構造であり、O（Log N）です。

于 2008-11-27T10:58:00.130 に答える
1

ハッシュ結合を使用するように設定することができます。実行プランを調べて、ハッシュ結合が実際に使用されていることを確認できます。ハッシュ結合が使用されている場合でも、SQL Serverは、個々のクエリの実行の一部として、最初にハッシュテーブルを作成します。インデックスはハッシュとして保存されることはなく、ツリーとしてのみ保存されると思います。

一般に、潜在的に大きな文字列またはバイナリブロブ（pipTheGeekが言及しているように）に対して完全一致を行わない限り、人工ハッシュ列を作成しません。文字列が大きすぎてインデックスキーに収まらない可能性があるため、これが必要になる場合があることを付け加えたいと思います。SQLServerの場合は2kのインデックスキーのサイズに制限があります。

もちろん、結合には、ハッシュに起因するあいまいさを解決するために、ハッシュ列とソース列を含める必要があります。

于 2008-11-27T10:35:47.880 に答える
0

ID フィールドが int の場合、ID フィールドのクラスター化インデックスよりもインデックス化された CHECKSUM を検索する利点はありません。どちらもクラスター化インデックス シークを行うためです。また、int 列の CHECKSUM は、常に列と同じ値を返します (つまり、CHECKSUM(535) = 535)。ただし、一般に、ID が長い文字列の場合、CHECKSUM ルックアップのパフォーマンスが向上します。

于 2008-11-25T18:44:32.000 に答える