(Отказ от ответственности: у меня минимальный опыт работы с MySQL)
Это должно быть где-то посередине.
Абсолютно самой низкой сложностью всей операции будет та, которая будет появляться при простом чтении всех записей по порядку, что является линейным процессом - O(n). Это операция ввода-вывода, и с этим ничего не поделаешь - современные системы кэширования в большинстве ОС могут помочь, но только в БД, которая используется и помещается в доступную память.
В большинстве движков SQL индексы представляют собой разновидность B-дерева. Сложность CPU при вставке одной записи в такое дерево примерно равна O(log(n)), где n - ее размер. Для n записей мы получаем сложность O(n log(n)). Общая сложность операции должна составлять O(n log(n)).
Конечно, не все так просто. Вычисление дерева индексов на самом деле не сильно загружает процессор, и поскольку страницы индексов должны помещаться в ОЗУ в любой современной системе, операция вставки одного узла , когда дерево не перебалансировано, будет близка к O(1) по времени: операция на одном диске для обновления конечной страницы индекса.
Поскольку дерево действительно перебалансировано, все, вероятно, немного сложнее. Несколько индексных страниц могут быть записаны на диск, что увеличивает необходимое время. Как грубое предположение, я бы сказал, O(n log(n)) - хорошее начало ...
Однако оно никогда не должно приближаться к экспоненциальной сложности.
EDIT:
Мне только что пришло в голову, что 70 000 000 записей B-дерева могут фактически не помещаться в кэш в памяти. Это будет сильно зависеть от того, что индексируется. INTEGER столбцы, вероятно, будут в порядке, но TEXT столбцы - это совсем другая история. Если средняя длина поля составляет 100 байт (например, HTTP-ссылки или 30 символов неанглийского текста UTF-8), вам потребуется более 7 ГБ памяти для хранения индекса.
Итог:
Если индекс помещается в кэш, то, поскольку построение индекса должно быть одной транзакцией БД, оно будет связано с вводом / выводом и будет приблизительно линейным, поскольку все записи должны быть проанализированы, а затем индекс сам по себе должен быть выписан на постоянное хранение.
Если индекс не помещается в кеше, сложность возрастает, так как время ожидания ввода-вывода для самого индекса включается в каждую операцию.