sql - 主キーが複合の場合のSQL Server検索アルゴリズムとは

Question

最良の検索アルゴリズムは二分探索木であることがわかっています。複合テーブルの主キーを考えてみましょう。SQL ServerBSTはデータの検索に使用しますか? はいの場合、どのように複数の列を検索できますBSTか? BSTそれが使用する他のアルゴリズム用量を使用しない場合は? そして、そのアルゴリズムの時間複雑度は何ですか?

あなたが知っていることを何でも共有してください:)

Answer 1

まったく同じ複雑さでまったく同じアルゴリズムを使用します。

'A'、'B'、'C' などの値を持つ 1 つのフィールド PK があると想像してみてください。問題ありませんよね?

これらのキーが代わりに「AA」、「BB」、「CC」などであると想像してみてください - 問題ありませんよね? これは単なる 2 文字のキーです。

複合 PK は、概念的に言えば、'A' と比較して 'AA' に似ています。PK が値「A」と「B」を持つ 1 文字の 2 つの列にまたがる場合、キーは単一列の値「AB」と比較される可能性があります。

簡単に言えば、キー比較は、1 つだけではなく X フィールドを比較するようになりました。

Answer 2

ツリー検索は、キーの抽象的な概念に依存します。キーは他のキーと比較できる必要があります。それだけです。検索アルゴリズムは、キーが複数のフィールドで構成されているかどうかを知る必要はありません。それが知っているのは、キーが比較可能であることだけです。