SELECT WHERE [主鍵] = [主鍵值] O（1）？

對於典型的現代關係型數據庫管理系統，通過一個特定的主鍵進行查詢的速度與通過關鍵字查詢哈希表一樣快是否正確？SELECT WHERE [主鍵] = [主鍵值] O（1）？

或者是否存在「實際工作」來遍歷表並追蹤主鍵值？即使主鍵有自動索引，這似乎也是無法想象的浪費。

2013-03-31 S. Valmont

它應該很快，但不一定是O（1）。許多數據庫索引是樹結構，而不是哈希表。 – Barmar

聽起來像你正在考慮通過主鍵上的自動索引進行樹搜索。這將是O（log n）。這會令人失望。沒有什麼個人，但我希望你錯了！ –

閱讀[第19章]（http://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC8QFjAA&url=http%3A%2F%2Fwww.aabu.edu .jo％2Ftool％2Fcourse_file％2Flec_notes％2F901331_Fundamentals_of_Database_Systems％2C_6th_Edition_％280136086209％29.pdf＆EI = Lj9ZUaHoEIjmrAeHn4C4CQ＆USG = AFQjCNGr81mTvpcjSnSPei0hWXIAsJCOfQ＆BVM = bv.44442042，d.bmk）算法查詢處理和優化 –

數據庫操作涉及訪問輔助內存單元（磁盤）。而實現效率的重要是減少塊訪問時間（而不是操作）。 Select查詢的複雜性取決於完成的優化類型。
由於您在關鍵屬性上提到了=，因此對文件排序的關鍵屬性（與primary index）進行了相等比較，二進制搜索是有效的（這比內搜索更有效）。二進制搜索通常訪問日誌_{（Br）塊，其中Br是塊文件的編號。（這是鍛造計算，您可能還需要訪問額外的索引塊）。}

它也取決於索引實現的類型。如果它通過多級或B實現，則訪問時間可以進一步減少，這取決於節點中密鑰的數量（進一步取決於塊中可容納多少個記錄）。

在啓發式優化中，通常DBMS系統會在表格目錄中存儲MAX，MIN，AVG和其他類型的信息。所以如果可以從目錄信息派生信息查詢執行時間可能是恆定的O（1）。

閱讀：第19章Algorithms for Query Processing and Optimization

來源

2013-03-31 09:13:52

實際上可以在讀取數據庫訪問結構，存儲結構和查詢優化後進行回答。 –

讓我們InnoDB存儲引擎。所有的InnoDB索引都是B樹。 B樹中最壞情況下的搜索複雜度爲O（log n）。但是，如果一張表幾乎完全適合主內存，InnoDB可以自動構建一個散列索引。 Adaptive Hash Indexes

來源

2013-03-31 09:18:53

SELECT WHERE [主鍵] = [主鍵值] O（​​1）？

回答

相關問題

SELECT WHERE [主鍵] = [主鍵值] O（1）？