Сложность добавления n записей в базу данных

Question

Какова сложность в больших обозначениях O добавления n записей в базу данных с m записями с i индексами в MySQL и последующей фиксации?

Answer 1

Вставка в таблицу MyISAM без индексов занимает O(n) (линейное) время.

Для вставки в таблицу InnoDB и в любой индекс требуется log(m) * O(n) (линейное время в зависимости от количества уже существующих записей) времени (при условии m >> n), поскольку InnoDB таблиц и индексов B-Trees.

Общее время является суммой этих значений.

Answer 2

Это будет зависеть от количества индексов, которые у вас есть в ваших таблицах, среди других факторов.

Каждая отдельная операция в базе данных имеет различную сложность. Например, временная сложность
для операций поиска B-Tree составляет O (log n), а время для фактического поиска зависит от того, выполняется ли сканирование таблицы, а именно O (n).

Я полагаю, что вы могли бы составить довольно сложное уравнение для того, что вы описываете. Вам придется учитывать каждую операцию в отдельности, и я не уверен, что это можно сделать детерминистическим способом, учитывая склонность систем баз данных к тому, чтобы решать, как они будут выполнять вещи, используя планы запросов и т. Д.