mysql - テーブル内のレコードを検索するための MySQL の時間の複雑さ

Question

MySQL に n 個のレコードを持つテーブルがあるとします。いくつかの基準 (id = n-1 など) に基づいてレコードを検索するための時間の複雑さはどのくらいでしょうか? それは線形の時間の複雑さですか、それとも一定の時間の複雑さを持っていますか? 前もって感謝します ：）

Answer 1

列にインデックスを付けると、レコードは二分木でソートされるため、非常に高速になります。私はすべての最適化に精通しているわけではありませんが、理論的には少なくとも O(log n) になります。

create indexMySQL コマンドでインデックスを作成できます。

create index id_index on MyTable (ID);

Answer 2

id で取得したインデックスの種類によって異なります。ただし、id が整数で n が定数の場合、id のインデックスを使用して log(n) で実行できます。