> Photo by Todd Quackenbush on Unsplash
引入沒有任何公式和計算機科學理論的B + Tree索引
如果您不是DBA或數據庫開發人員，則可能不知道數據庫索引的機制。 但是，只要您可以編寫一些SQL查詢，您就一定已經聽說過數據庫索引，并且知道索引可以提高SQL查詢的性能。
在本文中，我將嘗試使用最簡單的語言和圖表來說明B + tree索引如何改善SQL查詢的性能。 我以B + tree索引為例的原因是
· 大多數關系數據庫管理系統（例如MySQL，SQL Server和Oracle）都使用它
· 它可以提高大多數類型的SQL查詢的性能，而不是特定類型的性能
它看起來怎樣？
> Photo by Shane Hauser on Unsplash
讓我們簡化該指令，這是一個簡化的圖，說明了B + tree索引的結構。
在上面的B + Tree示例中，每個矩形代表硬盤中的一個塊，而藍色填充點代表將這些塊鏈接在一起的指針。
請注意，此圖出于演示目的極大地簡化了B + Tree，因為它假定每個硬盤塊只能包含2個鍵。 實際上，這將更大。
重要的是要了解如何構造B + tree索引。 我們需要知道，"葉子節點"級別假定具有創建此索引的字段的所有值。 在上面的示例中，很明顯，我們在此表列中只有9行，其值從1到9。
如果您對上述B + Tree的構建方式感興趣，請參閱我的另一篇文章：如何在數據庫中構建B + Tree索引？
它是如何工作的？
> Photo by Maria Krasnova on Unsplash
B + tree可以幫助大多數數據庫查詢方案，這也是其有用的原因。
均等測試查詢
假設我們的SQL查詢是在條件為"等于"的情況下檢索的，例如：
SELECT *FROM TABLEWHERE ID = 3
為了找到等于3的ID，按如下方式使用B +樹。
· 從樹的頂層開始，3小于5，因此我們需要使用數字5左側的指針
· 在下一級別，3在2到4之間，因此我們需要在中間使用指針
· 我們在葉子節點上有塊，這里有3個
查詢比較
如果我們的SQL查詢正在范圍內搜索怎么辦？ 例如，這是SQL查詢：
SELECT *FROM TABLEWHERE ID BETWEEN 3 AND 7
這是該過程的演示。
· 從樹的頂層開始，3小于5，因此我們需要使用數字5左側的指針
· 在下一級別，3在2到4之間，因此我們需要在中間使用指針
· 我們在葉子節點上有塊，這里有3個
· 由于我們要查詢比較數據，因此光標將繼續在該代碼塊中獲取，因此我們可以得到數字4
· 我們還沒有到7，所以光標將繼續轉到下一個（右）葉子節點塊
· 我們到達了下一個區塊，所以我們得到了數字5和6。但是它尚未完成，與上一步類似的機制將用于到達下一個區塊。
· 我們到達了包含數字7的下一個塊
· 我們已經達到范圍的上限，因此查詢完成
B +樹特征
> Photo by Cristina Gottardi on Unsplash
B + Tree索引的最重要特征是它由樹的葉節點級別和搜索關鍵字級別組成。
· 該索引列的所有值都出現在葉節點中。
· 非葉節點僅用于搜索目的，因此僅存在指向較低級別的指針。 換句話說，它們不能導致實際的數據輸入。
· 葉子節點中的每個鍵都有一個指向數據條目的額外指針，因此它可以導致光標查找/獲取數據行。
B + Tree如何提高性能？
> Photo by Anders Jildén on Unsplash
如以上示例所示，B + Tree適用于"相等"條件和比較條件。
非葉水平
可以看出，查詢僅需要通過非葉子節點上的搜索鍵來找到期望值。 因此，當在創建B + Tree索引的列上檢索SQL查詢時，僅需要經過幾個級別的非葉節點。
您必須考慮到非葉節點一定是一種開銷，并且當有很多數據行時，它會變慢，因為可能有許多非葉級別。
部分正確。 是的，需要掃描非葉節點以獲得期望值。 實際上，掃描次數完全等于非葉級別的數目。 但是，實際上，我們硬盤上的塊將比上述示例大得多。 通常，具有1000萬個條目的表可以放在只有3個非葉級別的B + Tree中。 即使表非常大，例如數十億規模，通常B + Tree的非葉級別數通常為4或5。
因此，使用B + Tree索引可以大大減少SQL查詢中掃描的硬盤塊的數量。
為什么要掃描的塊數很重要？
我想本文的讀者可能沒有計算機科學背景，所以我想對"塊"進行簡單的解釋對于更好地理解問題可能是必要的。
在我們的硬盤中，數據并不總是按順序存儲。 單個文件可能會拆分并存儲到不同的塊中。 因此，當我們讀取文件/數據集/表時，為了掃描整個文件，有必要在不同的塊之間跳轉。
通常，對于機械硬盤驅動器，有一個只能上下移動的磁頭。 當需要從其他位置讀取數據時，整個硬盤驅動器會將該位置旋轉到磁頭所在的位置，以便磁頭可以讀取數據。
想象一下，我們正在掃描1000個塊。 最壞的情況是磁盤將需要旋轉1000次。 如果我們使用索引，則此數字將減少為4-5次。 因此，索引可以提高效果。
摘要
> Photo by Aaron Burden on Unsplash
在本文中，我分享了B + tree的外觀以及它的工作方式和如何促進SQL查詢（通常在相等和比較的條件下）。
事實證明，B + Tree不再是最高級的數據庫索引，但我相信它可能是仍在大多數RDBMS中廣泛使用的最經典的索引，它仍然是證明為什么我們需要數據庫索引的最佳示例 表及其工作方式。 希望這對您足夠有趣。
(本文翻譯自Christopher Tao的文章《Why We Need Indexes for Database Tables》，參考：
https://towardsdatascience.com/why-we-need-indexes-for-database-tables-25198145a8ca)
