Возможно, Вам нужно "поиграть" с Fill Factor.
Если индекс кластерный а новые записи имеют не хронологический порядок (например случайный), Вам стоит резервировать для них место в базе, так, что бы не понадобилось реиндексировать их часто (база при этом потолстеет).
Кроме того, такое впечатление, что у Вас записи не оптимально распределены по страницам и экстенам. Проанализируйте (если Вы её разработчик) возможность максимально полного использования пространства страниц.