что такое индекс и как он работает? что происходит когда ты меняешь значение? Ну и еще от СУБД зависит. Например у PostgreSQL MVCC реализован таким образом, что апдейт это вставка на самом деле + отметка для предыдущей версии строки что мол оно уже не нужно (то что dead tuples). мы в любом случае должны взять наш btree и вставить в него новое значение с указателем на новый ряд. Вставка в btree это O(logn) как правило, то есть занимает время, пуская и не оч много. Ну и все это надо записать.
если бы индексы не накладывали оверхэда СУБД бы давно научились их автоматом генерировать на основе статистики