向數據庫中添加n個條目的複雜性

Question

在MySQL中添加了具有i索引的m條目並且事後提交的數據庫中添加n條目的大O符號的複雜性是什麼？

Answer 1

插入到沒有索引的MyISAM表中需要O(n)（線性）時間。

插入到InnoDB表，並進入任何索引需要log(m) * O(n)（線性時間取決於已經存在的記錄數）時間（假設m >> n），由於InnoDB表和索引是B-Trees。

總體時間是這些值的總和。

Answer 2

這取決於您在表格中的索引數量以及其他因素。

數據庫中的每個單獨操作都具有不同的複雜性。例如，B-Tree搜索操作的時間複雜度爲
爲O（log n），實際搜索的時間取決於表掃描是否發生，即O（n）。

我會想象你可以建立一個相當複雜的等式來描述你所描述的內容。由於數據庫系統傾向於以特定的方式決定他們如何使用查詢計劃執行事務等，所以您將不得不單獨考慮每項操作，並且我不確定是否可以以確定性方式完成。