索引是一種資料結構，可幫助MySQL高效獲取資料。
用於索引的常見資料模型是雜湊表、排序陣列和搜尋樹。
雜湊表
雜湊表是一種將資料儲存在鍵值（即鍵）中的結構，可以通過輸入要查詢的鍵來找到該鍵值。 這個想法是使用雜湊函式將鍵轉換為下標陣列，並將值儲存在下標的相應位置。 多個鍵值經過雜湊函式轉換後可能指向同乙個下標，因此使用鍊表來儲存同一下標對應的值。
以該人的身份證和姓名為例，如圖所示：
圖中key2和key3對應的陣列下標均為7，搜尋時，根據key2或key3的雜湊值定位陣列下標7，然後遍歷下標7對應的鍊表，找到key2或key3對應的value2或value3。 因此，雜湊表更適合等效值查詢。
有序陣列
以該人的身份證和姓名為例，如圖所示：
在圖中，有序陣列按 ID 號遞增的順序儲存
如果要查詢 card1 對應的名稱，可以使用二分法快速獲取 card1 對應的名稱 1，時間複雜度為 o（log（n））。
如果要查詢 card3 和 card4 之間的資料，可以先用二分法找到 card3（如果 card3 不存在，則查詢大於 card3 的第乙個資料），然後向右遍歷，直到找到第乙個大於 card4 的 ID 號並退出迴圈。
如果要將一段資料插入到有序陣列中，則需要將資料移動到記錄後面，這相對昂貴。
因此，有序陣列索引更適合靜態儲存引擎（即不再修改的資料）。
搜尋樹
1）二叉搜尋樹。
二叉搜尋樹的特點是父節點左側子樹中所有節點的值小於父節點的值，右側子樹中所有節點的值都大於父節點的值。
以該人的身份證和姓名為例，如圖所示：
圖中，如果要查詢 card1 對應的資料，搜尋順序如下：usera ->userb ->usere ->user1。 時間複雜度為 o（log（n））。
2）多分叉搜尋樹。
樹可以是二進位的，也可以是多分叉的。 polyfork 樹的每個節點都有多個子節點，子節點之間的大小保證從左到右遞增。 二叉樹是最有效的搜尋方法，但實際上大多數資料庫儲存不使用二叉樹，因為索引不僅在記憶體中，還需要寫入磁碟。
假設一棵有 100 萬個節點的二叉樹的高度為 20。 乙個查詢可能需要訪問 20 個資料塊，從磁碟隨機讀取資料塊需要 10 毫秒的定址時間。 對於具有 100 萬行的表，如果使用二叉樹儲存單行，則訪問單行可能需要 20 x 10 毫秒。 因此，為了使查詢訪問盡可能少的資料塊，必須使查詢程序訪問盡可能少的資料塊（即，使用 n 分叉樹，其中 n 取決於塊的大小）。
例如，如果使用 innodb 的整數字段索引，則此 n 幾乎為 1200。 當多分叉樹的樹高為 4 時，可以儲存 1200 個 3 值（即：1728000000）。 然後，在訪問儲存 10 億行資料的表整型字段索引時，最多隻需要訪問磁碟 3 次，大大減少了訪問磁碟的次數，提高了搜尋效率。
B+ 樹
在 InnoDB 中，B+ 樹用作索引模型。 表是按照主鍵的順序以索引的形式儲存的，這種儲存方式的表稱為索引組織表。
B+樹形結構，如圖所示
在影象中：淡黃色表示磁碟塊。
淺藍色表示資料項。
深藍色表示指向磁碟塊的指標。
其中，磁碟塊1包含：
資料項16和38。
指標 p1、p2、p3：
P1 表示磁碟塊小於 16。
P2 表示介於 16 和 38 之間的磁碟塊。
p3 表示大於 38 的磁碟塊。
真實世界的資料儲存在葉節點中（即）;非葉子節點不儲存真實資料，只儲存引導搜尋方向的資料項，例如資料表中實際不存在的資料項。
B+ 樹搜尋過程
在上圖中，要查詢資料項 27，搜尋過程如下：
1）磁碟塊1從磁碟載入到記憶體，此時發生io，在記憶體中使用二進位查詢確定資料項16和38之間的27，並且磁碟塊1的P2指標被鎖定，記憶體操作時間很短（與磁碟的io相比）可以忽略不計。
2）通過磁碟塊1中p2指標的磁碟位址將磁碟塊3由磁碟塊3載入到記憶體中，發生第二次io，27在25和32之間，鎖定磁碟塊3的p2指標。
3）磁碟塊8通過磁碟塊3中P2指標的磁碟位址由磁碟塊8載入到記憶體中，發生第三個io，同時，記憶體做二分搜尋找到27，查詢結束，總共三個io完成。
通常，乙個三層 B+ 樹可以表示數百萬個資料，如果數百萬個資料查詢只需要三個 IO，效能將大大提高如果沒有索引，則每個資料項必須 IO 一次，總共需要數百萬個 IO，並且查詢成本會非常高。
索引型別
根據 b+ 葉子節點的內容，索引型別分為主鍵索引和非主鍵索引
主鍵索引的葉節點儲存整行資料。 在 InnoDB 中，主鍵索引也稱為聚簇索引。
未按主鍵編制索引的葉節點儲存主鍵的值。 在 InnoDB 中，非主鍵索引也稱為二級索引。
對於主鍵索引查詢，只需按主鍵（例如 id）即可搜尋主鍵索引的 B+ 樹。
查詢非主鍵索引（公共索引），需要搜尋公共索引的b+樹獲取主鍵值，然後根據主鍵值搜尋主鍵索引的b+樹，獲取對應的資料。
因此，基於非主鍵索引的查詢需要再掃瞄乙個索引樹。 因此，應在應用程式中盡可能使用主鍵查詢。
建立表：
create table t_user( id int primary key, card int not null, name varchar(16), index idx_card(card))engine=innodb;哪裡：
id：主鍵索引。
card：普通索引。
索引維護
資料入到索引中，具體取決於插入位置，其變化如下：
插入資料到最後，資料將直接插入。
同時，如果插入資料所在的資料頁已滿，則需要申請新的資料頁，並將部分資料移動到新的資料頁，這個過程稱為頁面**。 因此，在中間插入資料除了影響效能外，還會影響資料頁的利用率。 也就是說，原本放在乙個資料頁上的資料需要分成兩個頁面，整體空間利用率降低50%左右。
注： 當兩個相鄰的資料頁由於刪除資料而利用率較低時，將合併資料頁。 此過程稱為頁面合併，以及將頁面合併為頁面的相反過程。
維護自增主鍵索引
自增主鍵是自增列上定義的主鍵，自增主鍵不是空主鍵自增。 插入資料時，不能指定 ID（自遞增列）的值，系統會獲取當前 ID 的最大值加 1 作為下一條記錄的 ID 值。
自增主鍵的插入資料模式符合增量插入場景，每插入一條新資料都是一次追加操作，不涉及移動其他記錄，不會觸發葉節點的頁面。
非自增主鍵索引維護
使用非自增主鍵插入資料時，一般不能保證資料有序插入，會因資料移動和分頁等原因影響插入效能。 同時，非自增主鍵占用的儲存空間（如身份證號）比較大，從上面的B+樹搜尋過程中可以看出，IO的數量取決於B+樹的高度h。 假設當前資料表的資料量為n，每個磁碟塊中的資料項個數為m，則樹高h=log（m+1）n，當資料量n固定時，m越大，h越小。 而 m = 磁碟塊（資料頁）的大小資料項的大小，磁碟塊大小是固定的，如果資料項占用的空間越少，則磁碟塊中儲存的資料項 m 越多，b+ 樹的高度 h 越低。
以上面的 t user 表為例，初始化表資料：
insert into t_user values(1,43252411115431,'南丘學生 1'),(2,43252411115432,'南秋同學2'),(3,43252411115433,'南秋同學3'),(5,43252411115435,'南秋同學 5'),(6,43252411115436,'南秋同學 6'),(8,43252411115438,'南秋同學 8'),(9,43252411115439,'南秋同學9');執行語句：
select * from t_user where card between 43252411115433 and 43252411115438;查詢過程，如圖所示：
處理過程：1）從卡片索引樹中查詢card=43252411115433的記錄，得到id=3。
2） 從主鍵 （id） 索引樹中找到 id = 3 對應的資料行。
3） 重複步驟 1 和 2，直到找到卡大於 43252411115438 的記錄，結束迴圈，並將查詢結果集返回給客戶端。
在前面的流程中，查詢卡索引樹 5 次，查詢回表的主鍵索引樹 4 次。
覆蓋索引是指索引中包含查詢語句的查詢結果，不需要返回表。 例如，如果 select id from t user where card between 43252411115433 and 43252411115438 exist，則查詢的 ID 值需要存在於 card 索引樹中，無需返回表即可直接獲取查詢結果。
使用覆蓋索引是一種常見的效能優化方法，因為它可以減少樹上的搜尋次數並顯著提高查詢效能。
指數最左邊的字首原則
最左邊的字首原則意味著當MySQL建立聯合索引時，將遵循最左邊的字首匹配原則（即最左邊在前），並從聯合索引的最左側檢索資料。
建立表：
create table t_user( id int primary key, name varchar(16), age int not null, gender varchar(1), index idx_name_age_gender(name,age,gender))engine=innodb;最左邊字首原則的示例：
搜尋 （'張'三、20、'f'如果名稱相同，則將比較年齡和性別以獲取檢索到的資料。
搜尋 （20，'f'這樣，當沒有名稱資料時，B+樹就無法確定下乙個搜尋方向，因為在構建搜尋樹時，名稱是第乙個比較因子，搜尋方向必須以名稱來確定下乙個搜尋方向。
搜尋 （'張三','f'對於這樣的資料，B+樹可以使用name來確定下乙個搜尋方向，但是缺少下乙個字段年齡，所以只能先查詢出name為張三的資料，然後再將資料與性別f進行匹配。
注意：最左邊的字首匹配規則可以是並集索引最左邊的 n 個字段，也可以是字串索引最左邊的 m 個字元。
指數下推原理
mysql5.6、引入索引條件下推，在索引遍歷過程中可以先判斷索引中包含的字段，直接過濾掉不滿足條件的記錄，減少表返回次數。
不帶索引下推，執行語句：
select * from t_user where name like '張';執行該過程，如圖所示：
在圖中，查詢過程將僅按順序使用名稱的第乙個單詞'張'記錄被取出並返回到表中。 因此，有必要回到表格 4 次。
索引被下推並執行語句：
select * from t_user where name like '張' and age=20;執行該過程，如圖所示：
在圖中，查詢過程將僅按順序使用名稱的第乙個單詞'張'取出記錄判斷年齡是否等於20歲，年齡不等於20的記錄直接判斷跳過。 因此，只需要返回 ID 為 3 和 4 的兩條記錄（2 次）。
閱讀推薦]更多精彩內容，如：
Redis 系列。
資料結構和演算法。
NACOS系列。
MySQL系列。
JVM 系列。
卡夫卡系列。
請移至【南秋】個人主頁參考。 內容不斷更新。
關於作者]熱愛科技、熱愛生活的老寶貝，專注J**A領域，關注【南秋同學】帶你一起學習、共同成長