SQL 表旁邊的鍵值

我有一個儲存如下數據的 SQL (MSSQL) 表，並id作為主鍵。

應用程序需要的檢索類型是一個 3 步過程。

1. 首先，獲取所有ids，其中col1, col2,col3具有一定的價值，並且validis 1，類似於：

select id
from table
where col1 = 'A' and col2 = 'B' and col3 = 'C' and valid = 1;

2. 然後，從 s 列表中，根據一些計算id選擇一個。id
3. id給定來自步驟 #2的單曲，檢索data.

問題

id如何加快在步驟 #1中查找所有s 的過程？因為在某個時候，表格將增長到 1000 萬+，並且查找速度會很慢。

一種方法是在 MSSQL 中對col1、col2、col3和valid列創建索引，以便查詢更快。但我相信它仍然是〜O（logN）。

我能想到的另一個解決方案是有一個後台程序來在 SQL 表旁邊創建一個鍵值數據庫。此後台程序將建構如下內容：

我想在 SQL 表旁邊創建鍵值索引的原因是因為與表的整體大小（~10M+）相比，有效記錄的數量可能相對非常少（~100）。所以我們不必搜尋/掃描無效記錄。對於鍵值，查找以及因此的步驟 #1 將是 O(1)。

我只是想知道這是否常見，或者是否有其他數據庫技術可以更好地支持這一點。

編輯

• 抱歉，我把問題簡單化了，可能會影響答案。該valid列實際上並不存在於原始 SQL 表中；它在執行時計算並儲存在另一個表中。@Akina 在關於valid列分區的評論中的回复（軟刪除？）應該仍然有幫助。

我不確定秋名的建議是否真的O(1)。我也相信您誤認為鍵值儲存解決方案確實是O(1)（假設同一個鍵存在多次）。但這都不重要，因為O(Log2(n))速度非常快。我想你可能低估了速度有多快。

這裡有一些數學：Log2(10 million) = ~23和23 nodes seeked through in a B-Tree < 100 key lookups。因此，在您的特定案例中，B-Tree 索引實際上更快。讓我們將表增加到 100 億條記錄。Log2(10 billion) = ~33. 在任何類型的現代硬體上搜尋 33 個節點都不到一毫秒的時間。

以下是一些真實的生活經驗：我在適度的硬體上處理過數十億行的表，並且從它們中讀取少量數據（例如 100 行）會立即返回（約 1 毫秒）。如果您感興趣的只是在任何給定時間的一小部分行，那麼您可以將表增加到會影響讀取性能的實際行數確實沒有。

所以我同意 Akina 對CREATE INDEX idx ON table (valid, col1, col2, col3). （在這種情況下，您指定列的順序實際上並不重要，因為它們都在您的查詢中使用並且都是相等謂詞。）

這裡的關鍵要點是不要試圖通過重新設計一個不常見的解決方案來過早地優化您的數據庫，否則您可能會錯過實用和標準的解決方案，例如 clssic 索引。

BTree 1 級單頁上的索引鍵數為 N。每個索引鍵都有一個指向下一級頁的頁指針。所以在第 2 級有 N 個頁面，每個頁面有 N 個索引鍵。等等

Level   Index Keys
1          N^1
2          N^2
3          N^3
4          N^4

那麼如果需要跨越M個key，需要多少層L呢？

N^L=M
ln(N^L)=ln(M)
L*ln(N)=ln(M)
L=ln(M)/ln(N)
L=log N (M)

請注意，在非葉級別上，記錄儲存（索引鍵、頁指針）和在葉級別上儲存（索引鍵、行定位器），並且可能包含列。

引用自：https://dba.stackexchange.com/questions/315672