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