數(shù)據(jù)庫之索引模塊

索引模塊除了是數(shù)據(jù)庫最重要的模塊之一，也是面試中最經(jīng)常被問到的，關(guān)于索引模塊常見問題如下：

• 為什么要使用索引
• 什么樣的信息能成為索引
• 索引的數(shù)據(jù)結(jié)構(gòu)
• 密集索引和稀疏索引的區(qū)別

為什么要使用索引：

數(shù)據(jù)庫中最小存儲單位通常是塊或者頁，每個塊里面都會包含多行數(shù)據(jù)。而我們在查詢一些沒有使用索引的數(shù)據(jù)時，通常都需要進(jìn)行全表掃描，也就是說需要加載所有的塊，然后逐個遍歷這些塊直到查找出我們需要查找的數(shù)據(jù)。可想而知這種查詢方式在數(shù)據(jù)量比較大的時候效率是比較慢的，所以我們很多時候都需要避免全表掃描。不過數(shù)據(jù)庫的設(shè)計者早已考慮到這一點所以引入了更高效的查詢機(jī)制，即使用索引。索引的靈感來自于字典，我們都知道字典會記錄一些關(guān)鍵信息，例如偏旁部首拼音等，我們通過這些關(guān)鍵信息就可以快速查找到那個字所在的頁面。而索引也是如此，數(shù)據(jù)庫能夠通過索引記錄的關(guān)鍵信息迅速定位目標(biāo)數(shù)據(jù)在哪個位置上，就可以避免全表掃描的發(fā)生。所以使用索引的目的就是為了讓查詢更高效。

什么樣的信息能成為索引：

主鍵id，唯一的字段，以及頻繁被作為查詢條件的字段，若同時多個字段頻繁作為查詢條件時可以對這幾個字段建立組合索引

索引的數(shù)據(jù)結(jié)構(gòu)：

通常是B+樹、Hash以及少數(shù)數(shù)據(jù)庫支持的BitMap

二叉查找樹

接下來簡單的說下索引的數(shù)據(jù)結(jié)構(gòu)，我們都知道索引最常用的數(shù)據(jù)結(jié)構(gòu)是B+樹，在介紹什么是B+樹之前，首先得了解二叉查找樹和B樹，并簡單說明一下為什么沒有采用二叉樹或B樹作為索引的數(shù)據(jù)結(jié)構(gòu)。

現(xiàn)在我們已經(jīng)知道給字段建立索引的目的是為了幫助我們快速定位到目標(biāo)數(shù)據(jù)所在的位置，若讓我們自己去設(shè)計索引的話，對于快速查找這個需求可能第一時間就會想到二叉查找樹之類的樹形數(shù)據(jù)結(jié)構(gòu)。所以本小節(jié)先介紹二叉查找樹，并一步一步地了解為何在眾多的樹形結(jié)構(gòu)中會采用B+樹作為索引的數(shù)據(jù)結(jié)構(gòu)。

二叉查找樹是一種常用的樹形數(shù)據(jù)結(jié)構(gòu)，二叉查找樹的每個節(jié)點最多只有左右兩個子節(jié)點，分別成為左子樹和右子樹，通常左子樹的元素小于它的父節(jié)點，而右子樹則大于它的父節(jié)點。位于最頂端的節(jié)點通常稱為根節(jié)點，二叉查找樹的查找算法是二分查找。下圖是一顆平衡二叉樹，所謂平衡二叉樹就是末端左右兩個節(jié)點的高度相差不超過1：

二叉查找樹由于同一級最多只能有兩個節(jié)點，且對磁盤IO沒有優(yōu)化，因為每次IO讀取都只能讀兩個節(jié)點，所以并不能達(dá)到較理想的查詢速度，不能作為索引的數(shù)據(jù)結(jié)構(gòu)。

B樹

由于二叉樹每次只能讀取兩個節(jié)點對磁盤IO沒有優(yōu)化，并且只有左右兩個查找路徑，樹的深度就會隨著日益增加的數(shù)據(jù)量而遞增，所以這時候就需要尋找一個每個層級可以有多個節(jié)點的多路樹形結(jié)構(gòu)，而B樹就符合該需求，B樹又稱為多路平衡查找樹，其大致結(jié)構(gòu)如下圖：

同一層有m個節(jié)點通常稱為m階，一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質(zhì)的樹：

1. 根節(jié)點至少有兩個子節(jié)點
2. 樹中每個節(jié)點最多含有m個子節(jié)點（m >= 2）
3. 除根節(jié)點和葉子節(jié)點外，其他每個節(jié)點至少有ceil(m/2)個子節(jié)點
4. 所有的葉子節(jié)點都位于同一層
5. 假設(shè)每個非終端節(jié)點中包含有n個關(guān)鍵字信息，其中：
   • Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序 K(i-1) < Ki
   • 關(guān)鍵字的個數(shù) n 必須滿足：[ceil(m / 2) - 1] <=n <= m - 1，即任意節(jié)點的關(guān)鍵字個數(shù)上限比它的子樹上限少一個，且對于非葉子節(jié)點來說任意節(jié)點的關(guān)鍵字個數(shù)比它的指向孩子的指針個數(shù)少一個
   • 非葉子節(jié)點的指針：P[1], P[2], ..., p[M]; 其中 P[1] 指向關(guān)鍵字小于 K[1] 的子樹①，P[M] 指向關(guān)鍵大于 K[M - 1] 的子樹②，其他 P[i] 指向關(guān)鍵字屬于 (K[i - 1], K[i]) 的子樹③

①：某節(jié)點最左子節(jié)點里關(guān)鍵字的值均小于該節(jié)點最左關(guān)鍵字的值
②：某節(jié)點最右子節(jié)點里關(guān)鍵字的值均大于該節(jié)點里所有關(guān)鍵字的值
③：某節(jié)點除左右以外所有子節(jié)點里關(guān)鍵字的值大小，均位于離該子節(jié)點指針最近的兩個關(guān)鍵字的值之間

B+樹

B 樹雖然已經(jīng)達(dá)到可以用作于索引數(shù)據(jù)結(jié)構(gòu)的標(biāo)準(zhǔn)，但是還有更好的替代品，那就是B+樹，從名字也可以看出B+樹相當(dāng)于是B樹的變體。其定義基本與B樹相同，除了：

1. 非葉子節(jié)點的子樹指針與關(guān)鍵字個數(shù)相同
2. 非葉子節(jié)點的子樹指針 P[i]，指向關(guān)鍵字值[K[i], K[i + 1])的子樹
3. 非葉子節(jié)點僅用來做索引，數(shù)據(jù)都保存在葉子節(jié)點中
4. 所有葉子節(jié)點均有一個鏈指針指向下一個葉子節(jié)點，葉子節(jié)點形成的鏈會按大小排序

B+樹結(jié)構(gòu)圖：

B+樹相比于B樹及其他樹形數(shù)據(jù)結(jié)構(gòu)來說，更適合用來做存儲索引，原因如下：

• B+ 樹的磁盤讀寫代價更低，B+ 樹由于非葉子節(jié)點只會存儲索引，因此B+ 樹的非葉子節(jié)點相對于B 樹來說更小，如果把所有同一內(nèi)部節(jié)點的關(guān)鍵字存儲在同一盤塊中，那么該盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多，一次性讀入內(nèi)存中的關(guān)鍵字也就越多，相對來說IO讀寫次數(shù)也就降低了
• B+ 樹的查詢效率更加穩(wěn)定，因為具體數(shù)據(jù)存儲在葉子節(jié)點中，所以無論查詢?nèi)魏螖?shù)據(jù)都需要從根節(jié)點走到葉子節(jié)點，那么所有查詢的長度也就相同，這樣每個數(shù)據(jù)查詢的效率就幾乎是相同的
• B+ 樹更有利于對數(shù)據(jù)庫的掃描，B 樹在提高了磁盤IO的同時并沒有解決遍歷元素效率低下的問題，而B+ 樹只需要遍歷葉子節(jié)點就可以解決對全部關(guān)鍵字信息的掃描，所以對數(shù)據(jù)庫中頻繁使用的范圍查詢來說B+ 樹更高效

Hash以及BitMap

除了上一小節(jié)所介紹的B+ 樹索引結(jié)構(gòu)之外，還有一個常用的Hash索引結(jié)構(gòu)。Hash稍微簡單一些，就是對索引的key進(jìn)行一次hash計算，然后就可以定位出數(shù)據(jù)存儲的位置，所以在某些特定場景來說Hash索引要比B+ 樹索引更高效。如圖：

既然理論上來說Hash索引要比B+ 樹索引更高效，但是為什么沒有成為主流索引結(jié)構(gòu)呢，這是因為Hash索引存在以下缺點：

• 因為hash的特性，所以僅僅能滿足 “=”，“IN”，不能使用范圍查詢
• 無法被用來避免數(shù)據(jù)的排序操作
• 不能利用部分索引鍵查詢，因為在使用組合索引的時候，Hash索引是將組合索引里的字段合并后再計算的hash值，而不是單獨計算的hash值。所以不使用組合索引里全部字段去查詢的話，Hash索引就無法被利用
• 不能避免表掃描，因為數(shù)據(jù)量大的時候就會有出現(xiàn)重復(fù)Hash較多的情況，那么就得拿出所有相同Hash值的數(shù)據(jù)來比較才能取到具體的數(shù)據(jù)，所以普遍來說數(shù)據(jù)量越大Hash索引的效率就越低
• 遇到大量Hash值相等的情況后性能并不一定就會比B+樹索引高

BitMap：

除了B+ 樹及Hash索引外，還有一種索引結(jié)構(gòu)就是BitMap，即位圖索引，但是僅有少量數(shù)據(jù)庫支持，所以這里僅做簡略提及。當(dāng)表中的某個字段只有幾種值的時候，例如存儲性別信息的字段之類的，在這種字段使用BitMap索引就是最佳的選擇。BitMap結(jié)構(gòu)圖如下：

但是BitMap有一個很大的缺陷就是鎖的粒度會非常的大，在新增和更新數(shù)據(jù)時，與該數(shù)據(jù)在同一個位圖的數(shù)據(jù)也會被鎖住。

密集索引和稀疏索引的區(qū)別

密集索引和稀疏索引的區(qū)別：

• 密集索引文件中的每個搜索碼值都對應(yīng)一個索引值
• 稀疏索引文件只為索引碼的某些值建立索引項
• 密集索引和稀疏索引的主要區(qū)別就是前者葉子節(jié)點保存完整的數(shù)據(jù)，而后者保存的是指向data的指針

密集索引和稀疏索引的區(qū)別圖：

密集索引：葉子節(jié)點保存的不僅僅是鍵值，還保存了位于同一行數(shù)據(jù)里其他列的信息，由于密集索引決定了表的物理排列順序，而一個表只能有一個物理排列順序，所以一個表只能創(chuàng)建一個密集索引

稀疏索引：葉子節(jié)點僅保存了鍵位信息，以及該行數(shù)據(jù)的地址或主鍵。所以需要通過數(shù)據(jù)的地址或主鍵才能進(jìn)一步定位到數(shù)據(jù)。

我們來看看具體到MySQL的主流存儲引擎：

• MyISAM：不管是主鍵索引、唯一索引還是普通索引都屬于稀疏索引，所以MyISAM只有稀疏索引，沒有密集索引。并且MyISAM中索引與數(shù)據(jù)是分開存儲的
• InnoDB：表只會有且只有一個密集索引，其他索引都是稀疏索引。并且InnoDB中索引與數(shù)據(jù)是存儲在同一個文件中的
  • 若一個主鍵被定義，該主鍵則作為密集索引
  • 若沒有主鍵被定義，該表的第一個唯一非空索引則作為密集索引
  • 若不滿足以上條件，InnoDB內(nèi)部會生成一個隱藏主鍵作為密集索引，這個隱藏的主鍵是一個6字節(jié)的自增列
  • 非主鍵索引存儲相關(guān)鍵位和其他對應(yīng)的主鍵值，包含兩次查找

InnoDB與MyISAM引擎的檢索流程對比：

索引額外問題之聯(lián)合索引最左匹配原則的成因

假設(shè)我們對A、B兩個字段建立聯(lián)合索引：(A, B)，此時該聯(lián)合索引的左邊是A而右邊是B，當(dāng)執(zhí)行where A = '' and B = '' 時會走這個(A, B)聯(lián)合索引，where A = ''也會走(A, B)聯(lián)合索引，但是where B = ''則不會走(A, B)聯(lián)合索引。這就是所謂的最左匹配原則

在最左匹配原則中，有如下說明：

1. 最左前綴匹配原則，非常重要的原則，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的順序可以任意調(diào)整。
2. =和in可以亂序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意順序，mysql的查詢優(yōu)化器會幫你優(yōu)化成索引可以識別的形式

我們來做個實驗，驗證下最左匹配原則。建表sql如下，該表中有一個聯(lián)合索引：

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;

當(dāng)where條件存在name字段時，會使用索引查詢：

當(dāng)where條件不存在name字段時，則不會使用索引查詢：

當(dāng)where條件存在name字段時，即便是亂序也會使用索引查詢，因為MySQL的執(zhí)行優(yōu)化器會自動調(diào)整順序以滿足使用索引的條件：

參考文章：

• Mysql中聯(lián)合索引的最左匹配原則
• Mysql聯(lián)合索引最左匹配原則

現(xiàn)在我們來回答一下最左匹配原則的成因：

MySQL創(chuàng)建聯(lián)合索引時，是先對聯(lián)合索引中最左字段的數(shù)據(jù)進(jìn)行排序，在最左字段排序的基礎(chǔ)上，再對后一個字段的數(shù)據(jù)進(jìn)行排序，類似于order by 字段1，order by 字段2 這樣的一種排序規(guī)則。所以聯(lián)合索引中最左字段是絕對有序的，而后一個字段則是無序的了，因此使用除最左字段以外的字段進(jìn)行條件查詢是利用不到索引的，這就是最左匹配原則的成因

索引額外問題之索引是建立越多越好嗎

答案是否定的，所謂物極必反：

• 數(shù)據(jù)量小的表不需要建立索引，建立索引會增加額外的索引維護(hù)開銷
• 數(shù)據(jù)變更需要維護(hù)索引，因此更多的索引意味著更多的維護(hù)成本
• 更多的索引也意味著需要更多的存儲空間