1

MySQL の 2 つのフィールドでテーブルを検索したい:

select * from table where  
90 < x and x < 100 and 
50 < y and y < 60

最適化された場合、この検索の効率はどのくらいですか? O(log(n))?

また、どのような種類のインデックスとアルゴリズムを実装するのでしょうか? (標準の B ツリーまたはハッシュ マップを使用する場合、O(n.log(n)) と言うのは正しいですか?)

ありがとう

4

1 に答える 1

1

MySQL の複雑さは予測できないことが多いため、Big-O 表記で表現することはほとんど意味がありません。アルゴリズムのパフォーマンスに関するコンピュータ サイエンスのタイプの理論は、このコンテキストでは完全に崩壊します。

最大の問題は I/O オーバーヘッドです。何らかのディスク アクセスが必要になるとすぐに、操作にかかる時間を知る方法がありません。システムの負荷に応じて、数ミリ秒または数秒かかる場合があります。

一般に、特定のシステムと構成のパフォーマンス特性を判断するためにベンチマークを行う必要がありますが、それでもアイデアが得られるだけです。

これらの Big-O アルゴリズムは、ワーキング セット全体がメモリ内にあり、関連するすべてのデータでアクセス時間が一貫している場合にのみ意味があります。

于 2012-10-10T14:40:41.687 に答える