私はデータベースにかなり慣れていないので、これがばかげた質問であれば許してください。
現代のデータベースでは、インデックスを使用して行にアクセスすると、O(1) の複雑さになると思います。しかし、別の列を選択するクエリを実行すると、O(1) または O(n) になりますか? データベースはすべての行を反復処理する必要がありますか?それとも、列ごとに並べ替えられたリストを作成しますか?
26658 次
8 に答える
4
答えはわかりませんが、big-O 表記法は、任意に大きいデータセット サイズのパフォーマンスを示すだけであることを覚えておいてください。
たとえば、データベース パフォーマンスのボトルネックは通常、ディスク シークです。したがって、作業データセットをメモリに保持できれば、パフォーマンスが大幅に向上します。Big-O 表記は、そのような最適化については何も教えてくれません。なぜなら、それらは有限のデータセットにのみ関連するからです。
于 2009-04-08T10:45:42.917 に答える
3
B ツリーは、バイナリ ツリーの複雑さである O(logN) を生成しません。
B ツリーは、ノードごとにブロック全体を持つように構成されているため、ノードが見つかると、1 回の I/O 操作でブロック全体を読み取ることができます。
ノードあたりの項目数 = ブロック係数 (#records/block){bfr} の場合、B ツリー最適化検索では、O(N) I/ ではなく O(log bfr÷2 +1 N) I/O 操作が生成されます。キーでレコードを検索する O 操作。
于 2014-08-07T01:08:59.193 に答える
0
データベースごとに、さまざまな種類のインデックス、さまざまな実行計画、およびさまざまな実装があります。リレーション データベースのコードのほとんどは、検索最適化アルゴリズムにあります。あなたの質問に対する答えは一つではありません。クエリがどのように実行されるかを知りたい場合は、ツールを使用して実行計画を視覚化できます。
于 2009-04-07T22:13:46.357 に答える
0
インデックスのないテーブル、データは非順序構造に保存されます。いくつかのデータを検索したい場合、「スキャン」を使用して、テーブルの最初から最後まですべてのデータをチェックします。
ケース 1: インデックスなしのクエリ テーブル、クエリ 1 レコード、SQL クエリ プラン ステップ: 「テーブル スキャン」すべてのデータ、O(N)
ケース 2: インデックスなしのクエリ テーブル、多数のレコードのクエリ、SQL クエリ プラン ステップ: 「テーブル スキャン」すべてのデータ、O(N)
インデックス付きのテーブル、データは B ツリー構造に保存されます。これは、(インデックス付きの列で) 1 つのデータを検索する場合、B ツリー構造を使用してデータを検索します。
ケース 3: インデックス付きの列を含むクエリ テーブル、クエリ 1 レコード、SQL クエリ プラン ステップ: "インデックス シーク"、O(LogN)
ケース 4: インデックス付きの列でテーブルをクエリし、多くのレコードをクエリし、
2 可能な場合、SQL クエリ オプティマイザーは "インデックス統計" を使用して、どのアクション ステップを使用する方が高速かを計算して判断します。
- (a) SQL クエリ プラン ステップ:「インデックス スキャン」、O(N)
- (b) SQL クエリ プラン ステップ: "インデックス シーク"、O(R LogN) [レコード数の R]
于 2021-09-17T10:26:14.327 に答える