MySql數據庫中索引的原理是什么

這篇文章給大家介紹MySql數據庫中索引的原理是什么，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。

一、數據結構及算法理論

Innodb存儲引擎實現索引數據結構的是B+樹，下面介紹幾個數據結構。一步一步地說明為什么應該使用B+樹。

1.1 B+樹索引

B+樹索引的結構與二叉樹很類似。鍵值快速找到數據。但是，B+樹種的B不是二叉，它表示平衡。注意：只有索引行。數據庫通過將頁面加載到存儲器中來檢索存儲器中的數據，最后檢索數據。

介紹二分搜索法。按排序（遞增或減少）的順序記錄，在搜索過程中通過跳轉查找。例如，示出了5、10、19、21、31、37、42、48、50、52的10個數量。

可以以三次搜索速度找到48。逐次搜索需要8次。對于上述10個數，依次檢索的平均檢索次數是5.5次，二分檢索法是2.9次，最壞的情況是按順序檢索的次數是10次，二分檢索的次數是4次。兩點搜索將innodb頁面Directory的插槽按主關鍵字的順序保存，對于每個具體記錄的查詢將頁面Directory分成兩部分進行檢索。

1.2 二叉查找樹

數字表示各節點的鍵的值。在樹里找。左子樹的鍵值總是小于跟的鍵值，右子樹的鍵值總是大于跟的鍵值。通過中序遍歷得到鍵值：2、3、5、6、7、8。

查找樹的平均查找次數為2.3次，但是查找樹是可以任意構建。和這樣調查順序是一樣的。因此，引用了取得二叉樹平衡的想法，AVL樹。

1.3 定義

符合查找樹的定義，其次必須滿足任何節點的左右兩個子樹的高度最大差為1。

二叉樹的平衡非常快，但是為了維持二叉樹的平衡，通常需要一次以上的左轉和右轉插入或更新后樹木的平衡。

1.4 B+樹特性

全部記錄在葉節點中，按順序保存，各葉節點（以頁為單位）在邏輯上連續保存，是雙向循環鏈表。

B+樹插入必須確認插入后的葉節點中的記錄還被排序，因此在插入時必須考慮以下三種情況。

數據庫中的一個特征是B。因此，在數據庫中，B+樹的高度通常在2～3層，也就是說，正在尋找某個鍵行的記錄。最多可以進行2～3次IO。普通盤每秒至少可以進行100次IO。

二、索引摘要和非編譯索引

集合索引和非集合索引的區別在于頁節點是否保存整個行的記錄。

2.1 聚集索引

InnoDB存儲引擎表是索引組織表，表格數據按主關鍵字順序保存。集合索引是從各表的主鍵制作B+樹，在葉節點中存儲有表整體的行記錄數據，因此索引聚集的葉節點也成為數據頁。此特性用于收集索引，索引表中的數據也被確定為索引的一部分。同時B+樹的數據結構相同。每個數據頁面通過雙向鏈接鏈接鏈接。

實際數據只由一個B+樹排列。因此，每個表格只有一個鏈接索引。在許多情況下，查詢優化器傾向于采用集中索引，因為它可以在索引的葉節點處直接找到數據。此外，由于定義了數據的邏輯順序，所以可以快速訪問對象范圍的查詢。查詢優化器可以很快地發現需要掃描某范圍的數據。注意各頁的記錄也用雙向鏈保持。

2.2 非聚集索引

也叫輔助索引。數據行中沒有全部數據。頁面節點除了關鍵字之外，每個頁面級別的索引都包含書簽。InnoDB記憶引擎告訴我們索引對應的行數據在哪里。因為InnoDB存儲引擎表是索引組織表，因此InnoDB存儲引擎的輔助索引書簽是該行的數據的集合索引鍵。圖是索引和輔助索引的關系。

用輔助索引檢索數據時，InnoDB存儲引擎創建循環輔助索引，用葉電平指針取得箭頭鍵索引的鍵，用主鍵索引找到完整的行記錄。例如，要在三個高度的輔助索引樹中查找數據，必須找到輔助索引的主關鍵字。期間是3次。如果索引樹的高度為3，則會檢索3次組合索引。要搜索有完整行數據的頁面，6次邏輯Io必須訪問最終數據頁面。

關于MySql數據庫中索引的原理是什么就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。