0

テーブル T があり、列 C が B ツリーによってインデックス付けされ、定数 k が指定されているとします。次のクエリの結果が n になると仮定します。

select count(*) from T where C > k;

MySQL(InnoDB) で、B ツリーによってインデックス付けされた列 C を使用してこのようなクエリを試してみたところ、n の値が大きいほど、クエリが遅くなることがわかりました。大きなテーブル (GB) では、数分も待たなければなりません。したがって、時間の複雑さは n に関して線形であると推測します。しかし、テーブルのサイズに関して対数時間で実行できる B ツリーの内部ノードに関する集計情報を格納するかどうかはわかっています。

対数ソリューションが実装された DBMS や、MySQL でのクエリ時間を短縮するためのトリックを誰か提案してもらえますか?

4

2 に答える 2

1

実行計画を見ないと何とも言えません。少なくともOracleでは、Cの異なる値に対して異なる実行計画を立てるために、列Cにもヒストグラムが必要です。

また、インデックスの深さは通常 3 ～ 5 です。対数の底は非常に大きいです。また、多くのデータベースは、テーブルから行を削除するときにチートを行うことに注意してください。通常、リーフ ノードは、既に削除された行を指している可能性があります。B ツリーで集計値を維持するのは無駄であり、うまくスケーリングできません。

さまざまな優れたインデックス オプションを備えたデータベースを探している場合は、PostreSQL を参照してください。

于 2014-09-26T07:30:33.000 に答える