數據庫查詢時間複雜度

Question

我對數據庫相當陌生，所以請原諒我，如果這是一個愚蠢的問題。在現代數據庫中，如果我使用索引來訪問一行，我相信這將是O（1）的複雜性。但是如果我做一個查詢來選擇另一列，它會是O（1）還是O（n）？數據庫是否必須迭代所有行，或者它是否爲每列創建了一個排序列表？

Answer 1

實際上，我認爲基於索引的訪問將是O（log（n）），因爲您仍然在通過B-Tree-esque組織搜索以獲得您的記錄。

Answer 2

你有索引。聚簇索引在磁盤上進行物理排序，每個表只能有一個。非聚簇索引是邏輯排序的，你可以有很多這些（小心不要濫用它，它可能會減慢寫操作）。 如果你的專欄沒有索引，那麼我認爲這是一個很好的逐行方法。

Answer 3

索引是按列計算的，所以如果在未索引列上使用where子句，它將執行所謂的表掃描，即O（n）。

Answer 4

要回答你的字面問題，是的，如果列上沒有索引，數據庫引擎將不得不查看所有行。

在更有趣的情況下，通過多列（無論是否帶有索引）進行選擇時，情況會變得更加複雜：如果查詢優化器選擇使用索引，那麼它將首先根據索引選擇行，然後應用其餘約束的過濾器。從而將第二次過濾操作從O（行數）減少到O（通過索引選擇的行數）。這兩個數字之間的比率被稱爲選擇性和一個重要的統計數據，當選擇使用哪個指數。

Answer 5

對於不同的數據庫，有不同類型的索引，不同的執行計劃和不同的實現。關係數據庫的大部分代碼都在搜索優化算法中。你的問題沒有一個單一的答案。當您想知道如何執行查詢時，您可以使用工具將執行計劃可視化。

Answer 6

我不知道答案，但請記住，big-O表示法僅爲您提供了數據集大小任意大的性能指示。

例如，數據庫性能的瓶頸通常是磁盤查找。因此，如果工作數據集可以保存在內存中，性能會大大提高。 Big-O符號不會告訴你有關這種優化的任何內容，因爲它們只與有限的數據集有關。

Answer 7

B樹不會產生O（logN），這是二叉樹的複雜度。

B樹的組織方式是每個節點都有一個完整的塊，因此一旦找到一個節點，單個I/O操作就可以讀取整個塊。對於每個節點的項目數=阻塞因子（＃records/block）{bfr}，B-Tree優化的搜索將產生O（日誌 _{bfr÷2 +1} N）I/O操作，而不是O（N）I/O操作通過密鑰尋找記錄。