Я ещё не разбираюсь в БД настолько хорошо, может быть там есть какие-то штуки, позволяющие это обойти. С другой стороны, точно знаю, бывают кейсы когда при интенсивности операций по БД выше некоторого порогового значения СУБД начинает забивать на индексы вообще. Интересная тема, курить-неперекурить 🙂
Начал смотреть, кажется, что на практике цена записи в таблицу с индексами будет, в лучшем случае, линейно кратна объёма таблицы, т.к. бинарные деревья, связанные списки и всё такое.
Поскольку индекс — суть позиция поля в сортированном массиве таких же полей, добавление нового поля не может не сдвинуть все позиции, идущие после.