Я не эксперт по SQL Server, но я работал со старшим инженером Microsoft над производительностью одной из наших систем. По его словам, MSSS находит страницу для вставки новой строки с помощью «сканирования свободного пространства» ... сканирования каждой страницы в поисках страницы с пробелом для вставки строки.
Если вы добавляете кластерный индекс в таблицу, вы заставляете данные перемещаться в одно конкретное место. Допустим, вы добавили столбец автономного номера в эту таблицу и сделали его кластеризованным индексом. Теперь MSSS не сканирует свободный блок, он знает, что 1000 MUST идут сразу после 999; так что вместо этого он выполняет обход индекса.
Я бы дал этому шанс. Не нужно слишком много времени, чтобы попробовать 4 или 5 миллионов строк.