時間のコストは、データをインデックス付きテーブルに挿入するときに一定ですか？

Question

選択するためのデータを保存するアーカイブテーブルを作成しました。

毎日、レコードのバッチをアーカイブテーブルに転送するプログラムがあります。インデックス化された列がいくつかあります。他の人はそうではありませんが。

私はバッチ挿入あたりの時間コストに関心があります：
- 最初のバッチ挿入： N1
-2番目のバッチ挿入： N2
-3番目のバッチ挿入： N3

問題は、N1、N2、およびN3がほぼ同じであるか、N3> N2> N1になるのでしょうか？

つまり、時間コストは一定または増分になり、いくつかのインデックスが存在しますか？

すべてのインデックスはクラスター化されていません。

アーカイブテーブル構造はこれです：

create table document (
   doc_id   int unsigned primary key,
   owner_id int,  -- indexed
   title    smalltext,
   country  char(2),
   year     year(4),
   time     datetime,

   key ix_owner(owner_id)
}

Answer 1

コストは増分になります、 O(log(n)).

実際には、インデックスサイズが特定のしきい値に達すると、インデックスページがキャッシュにフィットするのを停止すると、グラフをステップにします。

キャッシュのサイズは次のように定義されています key_buffer_size の MyISAM と innodb_buffer_pool_size の InnoDB.

このしきい値の前に、コストはメモリシーク時間に比例します。しきい値の後、コストはディスクシーク時間に比例します（すべてがを乗算しました。 log(n) もちろん）