SQL 索引解釋，Pt。 2

已發表: 2022-03-11

在SQL Indexes Explained的第一課中，我們學習了使用排序來加速數據檢索。 雖然在對行進行排序後我們的查詢執行速度更快，但排序涉及至少讀取每一行一次並移動它們。 這使得該方法比簡單地按順序讀取整個表更慢且效率更低。

合乎邏輯的結論似乎是我們應該維護給定表的排序副本——我們將正式稱之為 SQL索引，前綴為IX_ 。 第一篇文章中的檢索算法將適用，我們不需要在開始之前對錶進行排序。

索引作為表的排序副本

讓我們再次使用 Google 表格來看看這個想法的實際實現。 我們的預訂電子表格變成了包含相同數據的五張表格的集合。 每個工作表都根據不同的列集進行排序。

此處的練習旨在比上一篇 SQL 索引教程文章中的練習更簡單——它們可以通過感覺來完成，而不是通過計時器和行數來完成。 一些練習看起來非常相似，但這一次，我們正在探索：

  1. 使用單獨的索引而不是排序的主表時如何更有效地檢索數據
  2. 修改數據時如何保持每個索引和表的順序

前面的教程側重於讀取，但在許多常見的現實世界數據動態中——包括我們的酒店預訂——我們必須考慮索引對寫入性能的影響，無論是插入新數據還是更新現有數據。

初步練習：取消預訂

要了解使用排序表策略的 SQL 索引性能，您的任務是從 2020 年 8 月 22 日在酒店 4 中刪除客戶端 12 的預訂。請記住，您必須從所有副本中刪除一行表並保持正確的排序。

完畢？ 應該清楚的是，保留表的多個排序副本的想法並不像看起來那麼好。 如果您仍有任何疑問，您也可以嘗試重新插入剛剛刪除的預訂或更改現有預訂的日期。

雖然表的排序副本允許更快的檢索，但正如我們剛剛了解到的，數據修改是一場噩夢。 每當我們需要添加、刪除或更新現有行時，我們都必須檢索表的所有副本，找到一行和/或應該添加或移動它的位置，最後移動數據塊。

使用行地址的 SQL 索引

此電子表格包含使用不同方法的索引。 索引行仍然根據特定標准進行排序，但我們不會將所有其他信息保留在索引行中。 相反，我們只保留“行地址”，即“預訂”表中的行地址——代表表本身——在 H 列中。

所有 RDBMS 實現都使用操作系統級別的功能來使用物理地址快速找到磁盤上的塊。 行地址通常由塊地址加上行在塊中的位置組成。

讓我們做一些練習來了解這個索引設計是如何工作的。

練習 1：客戶的所有預訂

與第一篇文章一樣，您將模擬以下 SQL 查詢的執行：

 SELECT * FROM Reservations WHERE ClientID = 12;

同樣，有兩種合理的方法。 第一個是簡單地從 Reservations 表中讀取所有行並僅獲取符合條件的行：

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

第二種方法涉及從 IX_ClientID 表中讀取數據，對於任何符合條件的項目，根據 rowAddress 值在 Reservation 表中查找一行：

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

在這裡，表達式Get first row from由類似於上一篇文章中的循環實現：

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

您可以通過向下滑動直到找到一行來找到具有給定 rowAddress 的行，或者在 rowAddress 列上使用過濾器。

如果只返回少數保留，使用索引的方法會更好。 但是，由於要返回數百（有時甚至只是數十）行，直接使用 Reservations 表會更快。

讀取量取決於 ClientID 的值。 對於最大值，您必須讀取整個索引，而對於最小值，它位於索引的開頭。 平均值是行數的一半。

我們稍後會回到那部分並提出一個有效的解決方案。 現在，讓我們關注找到符合我們條件的第一行之後的部分。

練習 2：從給定日期開始的預訂數量

任務是使用新的索引設計計算 2020 年 8 月 16 日的簽到次數。

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

無論涉及多少行，使用適當索引進行計數的方法都優於表掃描。 原因是我們根本不需要訪問 Reservations 表——我們在索引本身中有我們需要的所有信息：

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

該算法與使用排序表的算法基本相同。 但是，索引行比表行短得多，因此我們的 RDBMS 必須從磁盤讀取更少的數據塊。

練習 3：刑事調查（給定酒店和日期範圍的客人名單）

讓我們準備一份 2020 年 8 月 13 日至 14 日抵達酒店 3 的客人名單。

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

我們可以從 Reservations 表中讀取所有行或使用可用的索引之一。 在對根據特定標準排序的表進行相同的練習後，我們發現索引IX_HotelID_DateFrom是最有效的。

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

我們可以設計一個更有效的索引嗎？

我們訪問該表是因為ClientID值，這是我們報告的客人列表所需的唯一信息。 如果我們在 SQL 索引中包含該值，我們根本不必訪問該表。 嘗試僅從此類索引IX_HotelID_DateFrom_ClientID中準備一個讀取列表：

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

當索引包含查詢執行所需的所有信息時，我們說索引覆蓋了查詢。

練習 4：客人姓名而不是 ID 的列表

客人 ID 列表對於調查犯罪的警官來說毫無用處。 我們需要提供名稱：

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

為了提供一個列表，除了Reservations表中的數據，我們還需要一個包含客人信息的Clients表，可以在這個 Google 表格中找到。

這個練習與前一個練習類似，方法也是如此。

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

表達式Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID可以通過表掃描或使用我們的索引來實現。 如果我們使用表掃描，對於While循環中的每個ClientID ，我們必須平均讀取Clients表中的一半行：

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

到目前為止我們所考慮的索引實現——讓我們稱之為“平面”索引實現——不會有太大幫助。 我們必須從索引中讀取相同數量的行（儘管行更小），然後使用RowAddress跳轉到Clients中的行：

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

注意：這裡， PK指的是“主鍵”，我們將在本系列的後面探討這個術語。

有沒有辦法在不必讀取這麼多行的情況下實現這一點？ 是的——這正是 B 樹索引的用途。

平衡樹 (B-tree) 索引

讓我們將Clients_PK_Flat中的行分成四行塊，並創建一個列表，其中包含塊中最後一個ClientID的值和塊開始的地址（列IndexRowAddress ）。 生成的數據庫索引數據結構——您可以在 Clients_PK_2Levels 表中找到。 試試新結構如何幫助您找到ClientID為 28 的客戶端。算法應如下所示：

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

您可能發現我們可以添加另一個級別。 級別 1 由四行組成，您可以在 IX_Clients_PK 選項卡中看到。 要找到 ClientID 為 28 的來賓名稱，您必須從主鍵結構中讀取三個數據塊（節點）（每層一個），最後跳轉到地址為 42 的 Clients 行。

這種 SQL 索引的結構稱為平衡樹。 當從根節點到每個葉級節點的路徑具有相同的長度時，樹是平衡的，即所謂的 B 樹深度。 在我們的例子中，深度是三。

基於電子表格中 IX_Clients_PK 選項卡的 B 樹示例，顯示了上述算法的查找路徑。

從現在開始，我們將認為每個索引都具有 B 樹結構，即使我們的電子表格僅包含葉級條目。 關於 B-tree 最重要的事實是：

  • B樹索引結構是市場上所有主要RDBMS最常用的索引。
  • 平衡樹的所有級別都按關鍵列值排序。
  • 數據以塊為單位從磁盤中讀取。
  • 一個 B 樹節點包含一個或多個塊。
  • 影響查詢性能的最重要因素是從磁盤讀取的塊數。
  • 每個新 B 樹級別中的項目數，從根開始，到葉級別結束，呈指數增長。

練習 5：刑事調查，第二部分

現在，巡視員正在從 A 市的所有酒店中查找相應客人的姓名、到達日期和酒店名稱的列表。

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

方法一

如果我們使用索引IX_DateFrom_HotelID_ClientID ，那麼對於日期範圍內的每一行，我們都必須訪問 Hotels 表並檢查酒店是否來自城市 A。如果是，我們也必須訪問 Clients 表，以讀客戶的名字。

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

方法二

使用IX_HotelID_DateFrom_ClientID為我們提供了更有效的執行計劃。

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

從Hotels表中，我們找到了城市 A 的所有酒店。知道了這些酒店的 ID，我們可以從IX_HotelID_DateFrom_ClientID索引中讀取後續項目。 這樣，在找到每個酒店和日期的 B 樹葉級別的第一行之後，我們就不會讀取 A 市以外的酒店的預訂信息。

將短 Hotels 表與 IX_HotelID_DateFrom_ClientID 索引結合使用。該表顯示在左側，突出顯示了兩行酒店，對應於城市 A 中的酒店。然後通過 B-tree 過程對這些酒店中的每一個進行快速查找，從而使它們直接指向索引中的塊在右側，所有搶手的數據都是連續的。

在這裡，我們可以看到，當我們擁有適合我們目標的數據庫索引時，額外的連接實際上可以使查詢更快。

當我解釋分區的動機及其影響時，將更詳細地討論 B 樹結構以及在插入、更新或刪除行時如何更新它。 關鍵是我們可以在使用索引時快速考慮這個操作。

SQL 中的索引查詢：細節決定一切

當涉及到索引和數據庫時，在 SQL 語言級別工作在一定程度上隱藏了實現細節。 這些練習旨在幫助您了解使用不同 SQL 索引時執行計劃的工作方式。 閱讀本文後，我希望您能夠根據可用索引和設計索引猜測最佳執行計劃，以使查詢盡可能快速和高效。

在本系列的下一部分中，我們將使用和擴展新獲得的技能來調查和了解在 SQL 中使用索引的最常見的最佳實踐和反模式。 我有一個好的和最佳實踐列表，我想在下一部分中討論，但是為了使下一篇文章更符合您的需求和經驗，請隨時發布您自己希望看到回答的問題。

在SQL 索引解釋的最後一部分，我們還將了解表和索引分區、使用它的正確和錯誤動機，以及它對查詢性能和數據庫維護的影響。