Complexité d'ajout de n entrées à une base de données

Question

Quelle est la complexité en notation O grand de l'ajout de n entrées à une base de données avec m entrées avec des index i dans MySQL et après avoir commis?

Answer 1

L'insertion dans une table MyISAM sans index prend O(n) (linéaire).

Insertion dans une table InnoDB et en tout indice prend log(m) * O(n) (temps linéaire en fonction du nombre de dossiers déjà existants) le temps (en supposant m >> n), puisque InnoDB tables et les index sont B-Trees.

Le temps global est la somme de ces valeurs.

Answer 2

Cela dépend du nombre d'index que vous avez dans vos tables, entre autres facteurs.

Chaque opération dans une base de données a une complexité différente. Par exemple, la complexité de temps
pour les opérations de recherche B-Tree est O (log n), et le temps pour une recherche réelle dépend de si un balayage de table a lieu, qui est O (n).

J'imagine que vous pourriez construire une équation qui est assez complexe pour ce que vous décrivez. Vous devrez rendre compte de chaque opération individuellement, et je ne suis pas sûr que cela puisse être fait de manière déterministe, étant donné la propension des systèmes de bases de données à décider de manière ad hoc comment exécuter des choses à l'aide de plans de requête, etc ...