表操作的表索引的算法順序
我無法清楚地表明表索引對錶操作的算法順序的影響。
我對具體實現的具體細節不感興趣；我假設 RDMS 設計人員知道他們在做什麼，並且他們已經使這些工作盡可能高效。
我將把我的討論限制在一個索引上，我認為額外的索引只是增加了一個額外的維度（即基本過程必須執行多次）。
以下假設在每種情況下都有一條記錄 - 索引的好處對於多個記錄操作大大增強，因為（通常）查找操作需要執行的次數少於正在查找的記錄數，因為它們可以在一個範圍內檢索。
對於未索引的表，我相信操作是：
Step INSERT SELECT DELETE UPDATE Find the record N/A O(n) O(n) O(n) Modify the record O(1) N/A O(1) O(1) OVERALL O(1) O(n) O(n) O(n)這假設查找記錄需要進行表掃描，但新記錄只是簡單地撞到最後。
建立索引是基於高效排序算法的 O(nlog(n)) 操作。
對於索引表，我相信操作是：
Step INSERT SELECT DELETE UPDATE Find the record N/A O(log(n)) O(log(n)) O(log(n)) Modify the record O(1) N/A O(1) O(1) Update the index O(log(n)) N/A O(1) O(1) OVERALL O(log(n)) O(log(n)) O(log(n)) O(log(n))這假設查找記錄現在是對索引的有序查找操作，更新索引是一個步驟，
DELETE並且UPDATE（因為您已經找到了記錄）和有序查找INSERT也就是說，插入變得更糟，但其他一切都變得更好。
它是否正確？
事情比這更複雜。這裡有幾點考慮。
首先，整個討論假設 B-Trees 或 B+ Trees（因此是 o(log(n))）。還有其他類型的索引，例如雜湊索引，其訪問時間為 O(1)。您的問題暗示您正在使用“等於”搜尋（例如尋找
X=17）查找值。但在這種特殊情況下，如果可能，最好使用雜湊索引。我同意你今天發現的大多數索引都是 B/B+ 樹，所以讓我們繼續這個假設。
您還含蓄地指出 a 中始終只有一個結果行
SELECT，這幾乎不是典型情況；很多時候，我們一次查找1,000行。但是讓我們繼續假設單個匹配行。您的下一個假設是搜尋始終由索引列完成。這很好，但我只是注意到
DELETE通過一些未索引的列獲取記錄Y結果更加昂貴：你們都在浪費 O(n) 時間來查找記錄，然後支付額外的 O(log(n )) 用於更新索引。但是讓我們繼續假設我們只討論正在查找索引列的查詢。
一些表使用非聚集索引格式（適合您的計算） - 表是一個實體，索引是另一個。其他人使用聚集索引格式：表行（或者更確切地說是行塊，或者更確切地說是行頁）實際上作為葉子儲存在聚集索引中。
INSERT在這種情況下，您將支付 O(log(n)) 以在命令中查找記錄。對此的優化是在您插入表末尾的情況下，一個體面的實現將保存指向索引中最後一條記錄/頁面的指針。（哦，是的，您的記錄不應該被INSERT編輯到表格的中間）。實際上，即使在非聚群表中，記錄也可以插入到表的中間；花更多的搜尋時間以避免碎片化是有意義的，並且至少我知道的一種實現可以做到這一點。我假設其他人也可能。
從 BTree 中刪除/插入索引平均為 O(1)，但在傳播頁面合併/拆分的情況下可能會花費多達 log(n) 次操作。
此外，總是讓許多人感到驚訝的事實是，有時表掃描比索引查找更快。對於導致多行的查詢尤其如此。事實證明，查找索引會增加成本；與全表掃描相比，成本實際上可能使總成本更高。對於單行查找，絕大多數索引查找應該比全表掃描更快。
但是請考慮以下一般約定：您用美元支付任何訪問磁碟的操作。您支付對記憶體數據起作用的五分錢行動。這實際上是數據庫磁碟 I/O 優化的核心。如果索引頁在磁碟上，而表頁恰好在記憶體中，您可能會為表掃描支付更少的費用。
這就是破壞的來源：這實際上完全取決於您的工作負載、記憶體大小和數據集大小。
你有沒有上過數學課，你必須解決一些複雜的積分？你花了好幾個小時才解決它，並因為在某處遺漏了一些微小的減號而被扣分？
你甚至上過物理課，你必須解決一些複雜的積分嗎？教授會扔掉方程式的大部分內容，說“這是可以忽略的”，而您會扯掉頭髮嗎？為什麼它可以忽略？為什麼不是其他的東西？
電腦科學以數學為基礎。電腦是基於物理學的。它們是物理對象。他們需要旋轉磁碟、訪問記憶體匯流排、管理數十億個晶體管……您實際上無法預測會發生什麼，並將其放在某個等式下。
事實證明，對於某些特定數據集，您的整個方程式並不成立。在其他時候，它可能會很好。