O（1）是否可以訪問數據庫行？

Question

我有一個使用自動增量字段（ID）作爲主鍵的表。該表只附加，不會刪除行。表格被設計爲具有恆定的行大小。因此，我期望O（1）訪問時間使用任何值作爲ID，因爲很容易計算在文件中查找的確切位置（ID * row_size），但不幸的是情況並非如此。

我使用的SQL Server。
它甚至有可能嗎？

由於

Answer 1

我想這對你很重要的事情是性能。 數據庫使用索引來訪問寫在磁盤上的記錄。

通常這與B +樹索引，它們是登錄完成 _b n其中b對於內部節點通常是100和200之間（優化塊大小，見ref）

這仍然嚴格地說對數性能，但是如果記錄數量相當多，比如說有幾百萬，那麼葉節點可以在3到4個步驟內完成，並且還有查詢計劃，會話啓動，鎖定等所有開銷（反正你會如果你需要多用戶，符合ACID標準的數據管理系統）肯定是出於所有可以與恆定時間相比的實際原因。

Answer 2

因此，我期望具有O（1）訪問使用任何值作爲ID 時間，因爲它是 容易計算精確的位置，以尋求在文件 （ID * row_size）

啊。不。自動增量不 - 即使沒有刪除 - 保證沒有漏洞。孔=通過索引查找。 Ergo：你的假設是錯誤的。

Answer 3

好消息是，一個索引讀取是O（日誌（N）），其對於n值很大變得相當接近O（1）。這就是說，在這種情況下，O符號不是很有用，實際的時間安排更加平庸。

Answer 4

即使它是可以直接解決行，查詢仍然要經過客戶端和服務器協議棧，並開展各種查詢和內存分配纔可以給你想要的結果。看起來你正在期待一些甚至不實際的事情。這裏真正的問題是什麼？ SQL Server對你來說不夠快嗎？如果是這樣，你可以使用許多選項來提高性能，但直接在文件中尋找地址不是其中的一個。

Answer 5

不可能的。 SQL Server根據鍵值和索引值將數據組織成樹狀結構;數據庫意義上的「索引」更像是參考書的索引，而不像數組或列表等索引數據結構。充其量，在搜索索引值時可以獲得對數性能（PK通常被視爲索引）。最壞情況是對非索引列的表掃描，它是線性的。在數據庫變得非常大之前，針對精心設計的表進行精心設計的查詢的查找時間與通過網絡或甚至命名管道發送它所需的時間相比將變得蒼白。