Mysql – Complexity of adding n entries to a database


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?

Best Solution

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.