B+樹索引搜尋（Index Seek）與索引掃描（Index Scan）

在本文中，我探讨了資料庫中索引搜尋（Index Seek）和索引掃描（Index Scan）的性能影響。雖然這些術語主要與 SQL Server 相關，但它們對于在資料庫管理系統（DBMS）平台中搜尋 B+樹非常重要。

搜尋還是掃描

索引搜尋通過從根節點開始周遊 B+樹，查找葉節點頁中的單個值。這至少需要 2 次I/O操作，具體取決于 B+樹的深度。而索引掃描通過掃描已經排序和連結的 B+樹葉節點頁來進行操作。

索引掃描更适用于範圍查詢或接近的大值，而索引搜尋适用于傳回非常少的結果或者更具選擇性的查詢。

為了更好地說明這一點，我們以學生表為例，其中包含了 ID 整數字段等。我們特别關注 ID 字段上的 B+樹索引。

假設一個頁面大小可以容納多達 2000 個元素（鍵值對），那麼結構可能如下所示。

讓我們看一些例子。

索引搜尋示例

考慮針對學生表的以下查詢：

SELECT *FROM STUDENTSWHERE ID = 1 OR ID = 5003 or ID = 9000

對于 ID 字段上的索引，該查詢需要執行 3 次索引搜尋，分别針對值 1、5003 和 9000。每個值都位于不同的頁面上，這意味着沒有緩存命中。

當然，一旦我們獲得了鍵值元素對，值将是指向表中所有字段的行 ID。這在資料庫系統之間有所不同，取決于 ID 是否是主索引以及是否是聚集索引。

注意：如果過濾條件中包含 ID = 2，那麼該條件将與存儲在同一頁上的值 1 滿足條件，是以我們已經擷取了它。緩存命中是關鍵。

索引掃描示例

在同一張表上，讓我們執行以下查詢：

SELECT *FROM STUDENTSWHERE ID BETWEEN 1000 and 9000

根據具體實作，該查詢可能會在範圍中的最低元素（1000）上執行搜尋，以找到最低頁，并沿着連結的葉子頁面周遊，直到達到具有條目9000的頁為止，此時索引掃描停止。

這是可能的，因為葉子頁面中的條目是有序的，并且彼此連結。

每個葉子頁面都指向下一個頁面，這是 B+Tree 的一個特性。

為什麼需要搜尋和掃描？

對于在1000到9000之間的每個值都進行搜尋會導緻更多的I/O，并且減慢查詢速度。而在第一個示例中，從具有值1的頁面到具有9000的頁面進行掃描，尋找1、5003和9000是一種IO浪費。資料庫最終會擷取不需要的頁面。

問題所在

在某些情況下，搜尋或掃描是顯而易見的，我上面提供的示例就是如此。但并非所有情況都如此簡單。

有些情況下，查詢優化器可能會根據内部查詢結果的結果選擇不同的計劃。

以查找分數高于90分的學生的完整學生行為例，這些成績存儲在單獨的表 STUDENTS_GRADES 中。

SELECT *FROM STUDENTSWHERE ID IN (SELECT ID FROM STUDENTS_GRADESWHERE GRADE > 90 )

内部查詢可能傳回單個值，也可能傳回散布在各處的數千個 ID。根據輸出結果，查詢優化器可能會選擇掃描或搜尋。

内部查詢結果集越大，使用索引的效率就越低。分散的 ID 将分布在許多頁面中，導緻過多的 I/O 操作。在某些情況下，為了避免不必要的 I/O 操作，查詢優化器可能會完全跳過索引而進行全表掃描。

坦率地說，我不喜歡結果不可預測的查詢，這隻會讓人感到困擾。我會盡量消除不可預測性，即使需要進行模式更改。

總結

你如何知道哪個更好？掃描還是搜尋？查詢優化器會盡力而為，但到最後可能會錯過并選擇錯誤的計劃。是以，如果可能的話，我們需要以可預測的方式編寫查詢。我知道這并不總是可能的，但了解背後發生的事情是第一步。

如果你喜歡我的文章，點贊，關注，轉發！