你知道數據庫索引的工作原理嗎？

點擊進入【碼農編程進階筆記】

免費獲取進階面試題、文檔、視頻資源

問：隨著數據庫的增大，既然索引的作用那么重要，有誰能拋開具體的數據庫來解釋一下索引的工作原理？

答：

數據在磁盤上是以塊的形式存儲的。為確保對磁盤操作的原子性，訪問數據的時候會一并訪問所有數據塊。磁盤上的這些數據塊與鏈表類似，即它們都包含一個數據段和一個指針，指針指向下一個節點（數據塊）的內存地址，而且它們都不需要連續存儲（即邏輯上相鄰的數據塊在物理上可以相隔很遠）。

鑒于很多記錄只能做到按一個字段排序，所以要查詢某個未經排序的字段，就需要使用線性查找，即要訪問N/2個數據塊，其中N指的是一個表所涵蓋的所有數據塊。如果該字段是非鍵字段（也就是說，不包含唯一值），那么就要搜索整個表空間，即要訪問全部N個數據塊。

然而，對于經過排序的字段，可以使用二分查找，因此只要訪問log2 N個數據塊。同樣，對于已經排過序的非鍵字段，只要找到更大的值，也就不用再搜索表中的其他數據塊了。這樣一來，性能就會有實質性的提升。

什么是索引

索引是對記錄按照多個字段進行排序的一種方式。對表中的某個字段建立索引會創建另一種數據結構，其中保存著字段的值，每個值又指向與它相關的記錄。這種索引的數據結構是經過排序的，因而可以對其執行二分查找。

索引的缺點是占用額外的磁盤空間。因為索引保存在MyISAM數據庫中，所以如果為同一個表中的很多字段都建立索引，那這個文件可能會很快膨脹到文件系統規定的上限。

索引的原理

首先，來看一個示例數據庫表的模式：

字段名??????????????數據類型?????????在磁盤上的大小

id?(Primary?key)???Unsigned?INT?????4?字節

firstName??????????Char(50)?????????50?字節

lastName???????????Char(50)?????????50?字節

emailAddress???????Char(100)????????100?字節

注意：這里用char而不用varchar是為了精確地描述數據占用磁盤的大小。這個示例數據庫中包含500萬行記錄，而且沒有建立索引。接下來我們就分析針對這個表的兩個查詢：一個查詢使用id（經過排序的鍵字段），另一個查詢使用firstName（未經排序的非鍵字段）。

示例分析一

對于這個擁有r = 5 000 000條記錄的示例數據庫，在磁盤上要為每條記錄分配 R = 204字節的固定存儲空間。這個表保存在MyISAM數據庫中，而這個數據庫默認的數據庫塊大小為 B = 1024字節。于是，我們可計算出這個表的分塊因數為 bfr = (B/R) = 1024/204 = 5，即磁盤上每個數據塊保存5條記錄。那么，保存整個表所需的數據塊數就是 N = (r/bfr) = 5000000/5 = 1 000 000。

使用線性查找搜索id字段——這個字段是鍵字段（每個字段的值唯一），需要訪問 N/2 ＝ 500 000個數據塊才能找到目標值。不過，因為這個字段是經過排序的，所以可以使用二分查找法，而這樣平均只需要訪問log2 1000000 = 19.93 = 20 個塊。顯然，這會給性能帶來極大的提升。

再來看看firstName字段，這個字段是未經排序的，因此不可能使用二分查找，況且這個字段的值也不是唯一的，所以要從表的開頭查找末尾，即要訪問 N = 1 000 000個數據塊。這種情況通過建立索引就能得到改善。

如果一條索引記錄只包含索引字段和一個指向原始記錄的指針，那么這條記錄肯定要比它所指向的包含更多字段的記錄更小。也就是說，索引本身占用的磁盤空間比原來的表更少，因此需要遍歷的數據塊數也比搜索原來的表更少。以下是firstName字段索引的模式：

字段名?????????數據類型????????在磁盤上的大小

firstName?????Char(50)????????50?字節

（記錄指針）????Special?????????4?字節

注意：在MySQL中，根據表的大小，指針的大小可能是2、3、4或5字節。

示例分析二

對于這個擁有r = 5 000 000條記錄的示例數據庫，每條索引記錄要占用 R = 54字節磁盤空間，而且同樣使用默認的數據塊大小 B = 1024字節。那么索引的分塊因數就是 bfr = (B/R) = 1024/54 = 18。最終這個表的索引需要占用 N = (r/bfr) = 5000000/18 = 277 778個數據塊。

現在，再搜索firstName字段就可以使用索引來提高性能了。對索引使用二分查找，需要訪問 log2 277778 = 18.09 = 19個數據塊。再加上為找到實際記錄的地址還要訪問一個數據塊，總共要訪問 19 + 1 = 20個數據塊，這與搜索未索引的表需要訪問277 778個數據塊相比，不啻于天壤之別。

什么時候用索引

創建索引要額外占用磁盤空間（比如，上面例子中要額外占用277 778個數據塊），建立的索引太多可能導致磁盤空間不足。因此，在建立索引時，一定要慎重選擇正確的字段。

由于索引只能提高搜索記錄中某個匹配字段的速度，因此在執行插入和刪除操作的情況下，僅為輸出結果而為字段建立索引，就純粹是浪費磁盤空間和處理時間了；這種情況下不用建立索引。另外，由于二分查找的原因，數據的基數性（cardinality）或唯一性也非常重要。對基數性為2的字段建立索引，會將數據一分為二，而對基數性為1000的字段，則同樣會返回大約1000條記錄。在這么低的基數性下，索引的效率將減低至線性查找的水平，而查詢優化器會在基數性小于記錄數的30%時放棄索引，實際上等于索引純粹只會浪費空間。

查詢優化器的原理：

查詢優化中最核心的問題就是精確估算不同查詢計劃的成本。優化器在估算查詢計劃的成本時，會使用一個數學模型，該模型又依賴于對每個查詢計劃中涉及的最大數據量的基數性（或者叫重數）的估算。而對基數性的估算又依賴于對查詢中謂詞選擇因數（selection factor of predicates）的估算。過去，數據庫系統在估算選擇性時，要使用每個字段中值的分布情況的詳盡統計信息，比如直方圖。這種技術對于估算孤立謂詞的選擇符效果很好。然而，很多查詢的謂詞是相互關聯的，例如select count(*) from R where R.make='Honda' and R.model='Accord'。查詢謂詞經常會高度關聯（比如，model='Accord'的前提條件是make='Honda'），而估計這種關聯的選擇性非常困難。查詢優化器之所以會選擇低劣的查詢計劃，一方面是因為對基數性估算不準，另一方面就是因為遺漏了很多關聯性。而這也是為什么數據庫管理員應該經常更新數據庫統計信息（特別是在重要的數據加載和卸載之后）的原因。

最后

如果這篇文章對您有所幫助，或者有所啟發的話，幫忙掃描下發二維碼關注一下，您的支持是我堅持寫作最大的動力。求一鍵三連：、轉發、在看

數據庫 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。