說到索引大家都不陌生,到底什麼是索引,索引又是如何工作的?
索引是應用程式設計和開發的一個重要方面。若索引太多,應用程式的性能可能會受到影響。而索引太少,對查詢性能又會產生影響。要找到一個合適的平衡點,這對應用程式的性能至關重要。
B+索引是最為常見,也是在資料庫中使用最為頻繁的一種索引。
什麼是索引
一句話簡單來說,索引的出現其實就是為了提高數據查詢的效率,就像書的目錄一樣。對於資料庫的表而言,索引其實就是它的「目錄」。
在MySQL中,索引是在存儲引擎層實現的,所以並沒有統一的索引標準,即不同存儲引擎的索引的工作方式並不一樣。而即使多個存儲引擎支持同一種類型的索引,其底層的實現也可能不同。
在InnoDB中,表都是根據主鍵順序以索引的形式存放的,這種存儲方式的表稱為索引組織表。InnoDB使用了B+樹索引模型,所以數據都是存儲在B+樹中的。
每一個索引在InnoDB裡面對應一棵B+樹。
B+樹索引
B+樹索引的本質就是B+樹在資料庫中的實現。
但是B+索引在資料庫中有一個特點是高扇出性,因此在資料庫中,B+樹的高度一般都在2-4層,這也就是說查找某一鍵值的行記錄時最多只需要2到4次IO,這倒不錯。因為當前一般的機械磁碟每秒至少可以做100次IO,2-4次的IO意味著查詢時間只需要0.02-0.04秒。
資料庫中的B+樹索引可以分為聚集索引和輔助索引,但是不管是聚集還是輔助索引,其內部都是B+樹的,即高度平衡的,葉子節點存放著所有的數據。
聚集索引與輔助索引不同的是,葉子節點存放的是否是一整行的信息。
B+樹的插入操作
B+樹是為磁碟或其他直接存取輔助設備設計的一種平衡查找樹。在B+樹中,所有記錄節點都是按鍵值的大小順序存放在同一層的葉子節點上,由各葉子節點指針進行連接。
先來看一個B+樹,其高度為2,每頁可存放4條記錄,扇出(fan out)為5,從圖5-6中可以看出,所有記錄都在葉子節點上,並且是順序存放的,如果用戶從最左邊的葉子節點開始順序遍歷,可以得到所有的鍵值的順序排序:5、10、15、20、25、30、50、55、60、65、75、80、85、90。
B+樹的插入必須保證插入後葉子節點中的記錄依然排序,同時需要考慮插入到B+樹的三種情況,每種情況都可能會導致不同的插入算法。
如上圖5-6的B+樹,若插入28這個鍵值,發現當前Leaf Page和Index Page都沒有滿,直接插入即可,如下圖
接著再插入70這個鍵值,這時原先的Leaf Page已經滿了,但是Index Page還沒有滿,符合第二種情況,這時插入Leaf Page後的情況為55、55、60、65、70,並根據中間的值60來拆分葉子節點,可得圖5-8。
最後插入鍵值95,這時符合第三種情況,即Leaf Page和Index Page都滿了,這時需要做兩次拆分,如圖5-9
可以看到,不管怎麼變化,B+樹總數會保持平衡。
但是為了保持平衡對於新插入的鍵值可能需要做大量的拆分頁(split)操作。
因為B+樹結構主要用於磁碟,頁的拆分意味著磁碟的操作,所以應該在可能的情況下儘量減少頁的拆分操作。
因此,B+樹同樣提供了類似於平衡二叉樹的旋轉(Rotation)功能。
旋轉發生在Leaf Page已經滿,但是其的左右兄弟節點沒有滿的情況下。這時B+樹並不會急於去做拆分頁的操作,而是將記錄移到所在頁的兄弟節點上。
在通常情況下,左兄弟會被首先檢查用來做旋轉操作,因此再來看圖,若插入鍵值70,其實B+樹並不會急於去拆分葉子節點,而是去做旋轉操作,得到如圖5-10所示的操作。
採用旋轉操作使B+樹減少了一次頁的拆分操作,同時這棵B+樹的高度依然還是2。
B+樹的刪除操作
B+樹使用填充因子(fill factor)來控制樹的刪除變化,50%是填充因子可設的最小值。
B+樹的刪除操作同樣必須保證刪除後葉子節點中的記錄依然排序。
同插入一樣,B+樹的刪除操作同樣需要考慮以下的三種情況,與插入不同的是,刪除根據填充因子的變化來衡量。
根據圖5-9的B+樹來進行刪除操作。首先刪除鍵值為70的這條記錄,該記錄符合第一種情況,刪除後可得到圖5-11。
接著刪除鍵值為25的記錄,這也是第二種情況,但是該值還是Index Page中的值,因此只刪除Leaf Page中的25後,還應將25的右兄弟節點的28
更新Page Index中,最後可得圖5-12。
最後看刪除鍵值為60的情況。刪除Leaf Page中鍵值為60的記錄後,Fill Factor小於50%,這時需要做合併操作,同樣,在刪除Index Page中相關
記錄後需要做Index Page的合併操作,最後得到圖5-13。
聚集索引
聚集索引就是按照每張表的主鍵構造一棵B+樹,同時葉子節點中存放的即為整張表的行記錄數據,也將聚集索引的葉子節點稱為數據頁。
聚集索引的這個特性決定了索引組織表中數據也是索引的一部分。
同B+樹數據結構一樣,每個數據頁都通過一個雙向鍊表來進行連結。
由於實際的數據頁只能按照一棵B+樹進行排序,因此每張表只能擁有一個聚集索引。
在多數情況下,查詢優化器傾向於採用聚集索引。
因為聚集索引能夠在B+樹索引的葉子節點上直接找到數據。
此外,由於定義了數據的邏輯順序,聚集索引能夠特別快地訪問針對範圍值的查詢。
查詢優化器能夠快速發現某一段範圍的數據頁需要掃描。
許多資料庫的文檔會這樣告訴讀者:聚集索引按照順序物理地存儲數據。
試想一下,如果聚集索引必須按照特定順序存放物理記錄,則維護成本顯得非常之高。
所以,聚集索引的存儲並不是物理上連續的,而是邏輯上連續的。
這其中有兩點:一是前面說過的頁通過雙向鍊表連結,頁按照主鍵的順序排序;另一點是每個頁中的記錄也是通過雙向鍊表進行維護的,物理存儲上可以同樣不按照主鍵存儲。
聚集索引的另一個好處是:他對主鍵的排序查找和範圍查找速度非常快。葉子節點的數據就是用戶所要查詢的數據。
輔助索引
對於輔助索引(Secondary Index,也稱非聚集索引),葉子節點不是包含行記錄的全部數據。葉子節點除了包含鍵值以外,每個葉子節點中的索引行中還包含了一個書籤(bookmark)。
該書籤用來告訴InnoDB存儲引擎哪裡可以找到與索引相對應的行數據。
由於InnoDB存儲引擎表是索引組織表,因此InnoDB存儲引擎的輔助索引的書籤就是相對應行數據的聚集索引鍵。
輔助索引的存在並不影響數據在聚集索引中的組織,因此每張表上可以有多個輔助索引。
當通過輔助索引來尋找數據時,InnoDB存儲引擎會遍歷輔助索引並通過葉級別的指針獲得指向主鍵索引的主鍵,然後再通過主鍵索引來找到一個完整的行記錄。
回到主鍵索引樹搜索的過程,我們稱為回表。
舉例來說:如果在一棵高度為3的輔助索引中查找數據,那需要對這棵輔助索引樹遍歷3次找到指定主鍵,如果聚集索引樹的高度同樣為3,那麼還需要對
聚集索引樹進行3次查找,最終找到一個完整的行數據所在的頁,因此一共需要6次邏輯IO訪問以得到最終的一個數據頁。
覆蓋索引
由於查詢結果所需要的數據只在主鍵索引上有,所以不得不回表。那麼,有沒有可能經過索引優化,避免回表過程呢?
InnoDB存儲引擎支持覆蓋索引(covering index,或稱索引覆蓋),即從輔助索引中就可以得到查詢的記錄,而不需要查詢聚集索引中的記錄。
使用覆蓋索引的一個好處是輔助索引不包含整行記錄的所有的信息,故其大小要遠小於聚集索引,因此可以減少大量的IO操作。
比如我們創建一個name列的輔助索引,而我們只需要查詢name。
如:select name from t where name="張三";
這時只需要查name的值,而name的值已經在name索引樹上了,因此可以直接提供查詢結果,不需要回表。也就是說,在這個查詢裡面,索引name已經「覆蓋了」我們的查詢需求,我們稱為覆蓋索引。
由於覆蓋索引可以減少樹的搜索次數,顯著提升查詢性能,所以使用覆蓋索引是一個常用的性能優化手段。
Index Condition Pushdown(ICP)優化
Index Condition Pushdown是MySQL 5.6開始支持的一種根據索引進行查詢的優化方式。
之前的MySQL資料庫版本不支持Index Condition Pushdown,當進行索引查詢時,首先根據索引來查找記錄,然後再根據WHERE條件來過濾記錄。
在支持Index Condition Pushdown後,MySQL資料庫會取出索引的同時,判斷是否可以進行WHERE條件過濾,也就是將WHERE的部分過濾操作放在了存儲引擎層。
在某些查詢下,可以大大減少上層SQL層對記錄的索取(fetch),從而提高資料庫的整體性能。
Index Condition Pushdown優化支持range、ref、eq_ref、ref_or_null類型的查詢,當前支持MyISAM和InnoDB存儲引擎。
當優化器旋轉Index Condition Pushdown優化時,可在執行計劃的列Extra看到Using index condition提示。
千鋒重慶Java培訓機構的課程採用100%全程面授教學,拒絕視頻同步授課,拒絕雙元視頻班教學,拒絕直播授課,教師一對一指導學員做項目,全新打造「主流技術+前沿技術+企業級聯動」教學課程,重新優化和定義JavaEE,採用最新版本技術開展教學,致力於為學員打造最牛的、最新的技術,助力學員拿下BAT級企業Offer。
選擇千鋒重慶Java培訓,將帶領你成功入門,走上Java開發工程師之路。