溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
索引模塊除了是數據庫最重要的模塊之一，也是面試中最經常被問到的，關于索引模塊常見問題如下：
為什么要使用索引：
數據庫中最小存儲單位通常是塊或者頁，每個塊里面都會包含多行數據。而我們在查詢一些沒有使用索引的數據時，通常都需要進行全表掃描，也就是說需要加載所有的塊，然后逐個遍歷這些塊直到查找出我們需要查找的數據。可想而知這種查詢方式在數據量比較大的時候效率是比較慢的，所以我們很多時候都需要避免全表掃描。不過數據庫的設計者早已考慮到這一點所以引入了更高效的查詢機制，即使用索引。索引的靈感來自于字典，我們都知道字典會記錄一些關鍵信息，例如偏旁部首拼音等，我們通過這些關鍵信息就可以快速查找到那個字所在的頁面。而索引也是如此，數據庫能夠通過索引記錄的關鍵信息迅速定位目標數據在哪個位置上，就可以避免全表掃描的發生。所以使用索引的目的就是為了讓查詢更高效。
什么樣的信息能成為索引：
主鍵id，唯一的字段，以及頻繁被作為查詢條件的字段，若同時多個字段頻繁作為查詢條件時可以對這幾個字段建立組合索引
索引的數據結構：
通常是B+樹、Hash以及少數數據庫支持的BitMap
接下來簡單的說下索引的數據結構，我們都知道索引最常用的數據結構是B+樹，在介紹什么是B+樹之前，首先得了解二叉查找樹和B樹，并簡單說明一下為什么沒有采用二叉樹或B樹作為索引的數據結構。
現在我們已經知道給字段建立索引的目的是為了幫助我們快速定位到目標數據所在的位置，若讓我們自己去設計索引的話，對于快速查找這個需求可能第一時間就會想到二叉查找樹之類的樹形數據結構。所以本小節先介紹二叉查找樹，并一步一步地了解為何在眾多的樹形結構中會采用B+樹作為索引的數據結構。
二叉查找樹是一種常用的樹形數據結構，二叉查找樹的每個節點最多只有左右兩個子節點，分別成為左子樹和右子樹，通常左子樹的元素小于它的父節點，而右子樹則大于它的父節點。位于最頂端的節點通常稱為根節點，二叉查找樹的查找算法是二分查找。下圖是一顆平衡二叉樹，所謂平衡二叉樹就是末端左右兩個節點的高度相差不超過1：
二叉查找樹由于同一級最多只能有兩個節點，且對磁盤IO沒有優化，因為每次IO讀取都只能讀兩個節點，所以并不能達到較理想的查詢速度，不能作為索引的數據結構。
由于二叉樹每次只能讀取兩個節點對磁盤IO沒有優化，并且只有左右兩個查找路徑，樹的深度就會隨著日益增加的數據量而遞增，所以這時候就需要尋找一個每個層級可以有多個節點的多路樹形結構，而B樹就符合該需求，B樹又稱為多路平衡查找樹，其大致結構如下圖：
同一層有m個節點通常稱為m階，一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質的樹：
ceil(m/2)個子節點Ki (i=1...n)為關鍵字，且關鍵字按順序升序排序 K(i-1) < Ki[ceil(m / 2) - 1] <=n <= m - 1，即任意節點的關鍵字個數上限比它的子樹上限少一個，且對于非葉子節點來說任意節點的關鍵字個數比它的指向孩子的指針個數少一個①：某節點最左子節點里關鍵字的值均小于該節點最左關鍵字的值
②：某節點最右子節點里關鍵字的值均大于該節點里所有關鍵字的值
③：某節點除左右以外所有子節點里關鍵字的值大小，均位于離該子節點指針最近的兩個關鍵字的值之間
B 樹雖然已經達到可以用作于索引數據結構的標準，但是還有更好的替代品，那就是B+樹，從名字也可以看出B+樹相當于是B樹的變體。其定義基本與B樹相同，除了：
[K[i], K[i + 1])的子樹B+樹結構圖：
B+樹相比于B樹及其他樹形數據結構來說，更適合用來做存儲索引，原因如下：
除了上一小節所介紹的B+ 樹索引結構之外，還有一個常用的Hash索引結構。Hash稍微簡單一些，就是對索引的key進行一次hash計算，然后就可以定位出數據存儲的位置，所以在某些特定場景來說Hash索引要比B+ 樹索引更高效。如圖：
既然理論上來說Hash索引要比B+ 樹索引更高效，但是為什么沒有成為主流索引結構呢，這是因為Hash索引存在以下缺點：
BitMap：
除了B+ 樹及Hash索引外，還有一種索引結構就是BitMap，即位圖索引，但是僅有少量數據庫支持，所以這里僅做簡略提及。當表中的某個字段只有幾種值的時候，例如存儲性別信息的字段之類的，在這種字段使用BitMap索引就是最佳的選擇。BitMap結構圖如下：
但是BitMap有一個很大的缺陷就是鎖的粒度會非常的大，在新增和更新數據時，與該數據在同一個位圖的數據也會被鎖住。
密集索引和稀疏索引的區別：
密集索引和稀疏索引的區別圖：
密集索引：葉子節點保存的不僅僅是鍵值，還保存了位于同一行數據里其他列的信息，由于密集索引決定了表的物理排列順序，而一個表只能有一個物理排列順序，所以一個表只能創建一個密集索引
稀疏索引：葉子節點僅保存了鍵位信息，以及該行數據的地址或主鍵。所以需要通過數據的地址或主鍵才能進一步定位到數據。
我們來看看具體到MySQL的主流存儲引擎：
InnoDB與MyISAM引擎的檢索流程對比：
假設我們對A、B兩個字段建立聯合索引：(A, B)，此時該聯合索引的左邊是A而右邊是B，當執行where A = '' and B = '' 時會走這個(A, B)聯合索引，where A = ''也會走(A, B)聯合索引，但是where B = ''則不會走(A, B)聯合索引。這就是所謂的最左匹配原則
在最左匹配原則中，有如下說明：
- 最左前綴匹配原則，非常重要的原則，mysql會一直向右匹配直到遇到范圍查詢(>、<、between、like)就停止匹配，比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)順序的索引，d是用不到索引的，如果建立(a,b,d,c)的索引則都可以用到，a,b,d的順序可以任意調整。
- =和in可以亂序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意順序，mysql的查詢優化器會幫你優化成索引可以識別的形式
我們來做個實驗，驗證下最左匹配原則。建表sql如下，該表中有一個聯合索引：
CREATE TABLE `student` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`name` varchar(20) NOT NULL,
`age` int(11) NOT NULL,
`sex` varchar(20) NOT NULL,
`address` varchar(100) NOT NULL,
`cid` int(11) NOT NULL,
PRIMARY KEY (`id`) USING BTREE,
KEY `idx_name_age` (`name`,`age`)
) ENGINE=InnoDB AUTO_INCREMENT=19 DEFAULT CHARSET=utf8;當where條件存在name字段時，會使用索引查詢：
當where條件不存在name字段時，則不會使用索引查詢：
當where條件存在name字段時，即便是亂序也會使用索引查詢，因為MySQL的執行優化器會自動調整順序以滿足使用索引的條件：
參考文章：
現在我們來回答一下最左匹配原則的成因：
MySQL創建聯合索引時，是先對聯合索引中最左字段的數據進行排序，在最左字段排序的基礎上，再對后一個字段的數據進行排序，類似于order by 字段1，order by 字段2 這樣的一種排序規則。所以聯合索引中最左字段是絕對有序的，而后一個字段則是無序的了，因此使用除最左字段以外的字段進行條件查詢是利用不到索引的，這就是最左匹配原則的成因
答案是否定的，所謂物極必反：
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
