Complexity of adding n entries to a database

Question

What the complexity in big O notation of adding n entries to a database with m entries with i indexes in MySQL and afterwards committing?

Answer 1

That would depend on the number of indexes you have in your tables, among other factors.

Each individual operation in a database has a different complexity. For example, the time complexity
for B-Tree search operations is O(log n), and the time for an actual search depends on whether a table scan takes place, which is O(n).

I would imagine that you could build an equation that is quite complex for what you are describing. You would have to account for each operation individually, and I'm not sure that can be done in a deterministic way, given database systems' propensity for deciding in an adhoc way how they will execute things using query plans, etc.

Answer 2

Inserting into a MyISAM table without indexes takes O(n) (linear) time.

Inserting into an InnoDB table and into any index takes log(m) * O(n) (linear time depending on the number of already existing records) time (assuming m >> n), since InnoDB tables and indexes are B-Trees.

Overall time is the sum of these values.