什麼是Big-O for SQL select？

對於具有n行的表以及我想返回m結果的表，SQL選擇的Big-O是什麼？什麼是Big-O for SQL select？

什麼是Update或delete或Create操作的Big-O？

我在說一般的mysql和sqlite。

2009-08-28 Graviton

重複：http://stackoverflow.com/questions/727719/database-query-time-complexity – 2009-08-28 22:23:07

由於您不控制選擇的算法，因此無法直接知道。但是，如果沒有索引，SELECT應該是O（n）（表掃描必須檢查每個記錄，這意味着它將隨着表的大小進行縮放）。

對於索引，SELECT可能是O（log（n））（儘管這取決於用於索引的算法以及數據本身的屬性，如果這對任何實際表都適用）。要確定任何表或查詢的結果，必須求助於分析真實世界的數據。

沒有索引的INSERT應該非常快（接近O（1）），而UPDATE需要首先查找記錄，因此比SELECT更慢（略微）。

當索引樹需要重新平衡時，帶索引的INSERT可能會再次出現在O（log（n^2））的範圍內，否則更接近於O（log（n））。如果在SELECT成本的基礎上影響索引行，UPDATE將會發生同樣的減速。

一旦你在討論加入混合，所有的注單都關閉：你將不得不分析和使用你的數據庫查詢估算工具來閱讀它。另請注意，如果此查詢對性能至關重要，則您應該不時查看re配置文件，因爲查詢優化器使用的算法會隨着數據負載的變化而發生變化。

要記住的另一件事是......大O不會告訴你每筆交易的固定成本。對於較小的表格，這些可能高於實際工作成本。舉個例子：單行交叉網絡查詢的設置，拆卸和通信成本肯定比查詢小表中的索引記錄要多。

因此，我發現能夠在一個批次中捆綁一組相關查詢可以對性能的影響遠遠超過我對數據庫本身所做的任何優化。

2009-08-28 15:03:58 Godeke

根據與加入選擇順序的評論，請記住用雙連接選擇一個表的選擇可以是n^2。例如; select * from table where id>（從表中選擇avg（id））可能會增加每個記錄的平方，而不使用索引。 – 2014-12-15 23:10:57

我認爲真正的答案只能根據具體情況確定（數據庫引擎，表格設計，指標等）。但是，如果您是MS SQL Server用戶，則可以熟悉查詢分析器（2000）或Management Studio（2005+）中的預計執行計劃。這爲您提供了大量可用於分析的信息。

2009-08-28 15:06:10

這一切都取決於您編寫SQL的方式以及數據庫針對您正在執行的操作而設計的程度。嘗試使用解釋計劃函數來查看數據庫將如何執行。的。你可以計算大-O

2009-08-28 15:09:20 beggs

回答