在MySQL中添加了具有i索引的m條目並且事後提交的數據庫中添加n條目的大O符號的複雜性是什麼?向數據庫中添加n個條目的複雜性
1
A
回答
2
插入到沒有索引的MyISAM
表中需要O(n)
(線性)時間。
插入到InnoDB
表,並進入任何索引需要log(m) * O(n)
(線性時間取決於已經存在的記錄數)時間(假設m >> n
),由於InnoDB
表和索引是B-Trees
。
總體時間是這些值的總和。
1
這取決於您在表格中的索引數量以及其他因素。
數據庫中的每個單獨操作都具有不同的複雜性。例如,B-Tree搜索操作的時間複雜度爲
爲O(log n),實際搜索的時間取決於表掃描是否發生,即O(n)。
我會想象你可以建立一個相當複雜的等式來描述你所描述的內容。由於數據庫系統傾向於以特定的方式決定他們如何使用查詢計劃執行事務等,所以您將不得不單獨考慮每項操作,並且我不確定是否可以以確定性方式完成。
相關問題
- 1. PHP - 添加多個數據庫條目
- 2. 從文件中向數據庫表添加條目
- 3. 向Mongo添加複雜類
- 4. 添加n個數字的時間複雜度是多少
- 5. 向我的訪問數據庫中添加重複數據行
- 6. 核心數據以編程方式向條目添加屬性
- 7. 重複數據庫條目
- 8. 向數據庫添加一系列條目
- 9. 將複選框添加到數據庫中的每個項目
- 10. 複雜的Mysql數據庫加入
- 11. 複雜性O(kM(n))多項式的複雜性?
- 12. wordpress不存儲數據,僅向數據庫添加新的空白條目
- 13. 複雜的MySQL數據庫
- 14. 從一個表單向數據庫添加多條記錄?
- 15. PHP:根據n生成n個頁面n數據庫中的項目數
- 16. 如何向條目數組中添加/刪除條目?
- 17. 數據庫錯誤:重複的條目
- 18. 處理重複的數據庫條目
- 19. 重複條目的數據庫錯誤
- 20. 來自數據庫的重複條目
- 21. 防止重複的數據庫條目
- 22. MySql添加到數據庫中的現有條目
- 23. 每次添加ListView數據庫中的新條目
- 24. 在Joomla的僞元素操作中添加數據庫條目
- 25. 向ListView添加新條目
- 26. 將多個文本框條目添加到mysql數據庫
- 27. 通過php表格添加多個條目到mysql數據庫
- 28. 複雜型內DDD項目的數據庫,第一個模型
- 29. MySQL - 將數據添加到數據庫的每個條目的命令?
- 30. 將n個數字插入二叉搜索樹的複雜性
我添加了這樣一個事實,即表中有我索引的問題。 – Christian 2009-09-18 11:56:13