典型的な最新の RDBMS では、1 つの特定の主キーによるクエリが、キーによるハッシュテーブルのクエリと同じくらい高速であると期待するのは正しいでしょうか?
それとも、テーブルをトラバースして主キーの値を追跡するために「実際の作業」が行われていますか? 主キーの自動インデックスがあるとしても、それは考えられないほど無駄に思えます。
2 に答える
1
データベースの操作には、二次記憶装置 (ディスク) へのアクセスが含まれます。また、効率を達成するために重要なのは、ブロック アクセス時間 (操作ではなく) を短縮することです。Select クエリの複雑さは、実行された最適化の種類によって異なります。
キー属性について述べ=たので、ファイルが順序付けられているキー属性の等値比較 (プライマリ インデックスを使用) では、二分検索が効率的です (内部検索よりも効率的) が使用されます。バイナリ検索は通常、log 2 (Br) ブロックにアクセスします。ここで、Br はファイルのブロック数です。(これは、インデックス用の余分なブロックにもアクセスする必要があるかもしれない精巧な計算です)。
また、インデックスの実装の種類にも依存します。マルチレベルまたはB、B +を介して実装されている場合、ノード内のキーの数に応じてアクセス時間がさらに短縮される可能性があります(さらに、ブロックに収容できるレコードの数に依存します)。
ヒューリスティック タイプの最適化では、通常、DBMS システムは MAX、MIN、AVG、およびその他の種類の情報をテーブル カタログに格納します。したがって、カタログ情報から情報を取得できる場合、クエリの実行時間は一定の O(1) になる可能性があります。
読む: 第 19 章クエリ処理と最適化のアルゴリズム
于 2013-03-31T09:13:52.813 に答える
0
InnoDB ストレージ エンジンを見てみましょう。すべての InnoDB インデックスは B ツリーです。B ツリーでの最悪の場合の検索の複雑さは O(log n) です。しかし、テーブルがほぼ完全にメイン メモリに収まる場合、 InnoDB は自動的にハッシュ インデックスを構築できます。適応ハッシュ インデックス
于 2013-03-31T09:18:53.723 に答える