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

衡山ssl適用于網(wǎng)站、小程序/APP、API接口等需要進(jìn)行數(shù)據(jù)傳輸應(yīng)用場(chǎng)景，ssl證書未來市場(chǎng)廣闊！成為創(chuàng)新互聯(lián)公司的ssl證書銷售渠道，可以享受市場(chǎng)價(jià)格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18980820575（備注：SSL證書合作）期待與您的合作！

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

為什么要使用索引：

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

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

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

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

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

---

二叉查找樹

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

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

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

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

---

B樹

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

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

1. 根節(jié)點(diǎn)至少有兩個(gè)子節(jié)點(diǎn)
2. 樹中每個(gè)節(jié)點(diǎn)最多含有m個(gè)子節(jié)點(diǎn)（m >= 2）
3. 除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外，其他每個(gè)節(jié)點(diǎn)至少有ceil(m/2)個(gè)子節(jié)點(diǎn)
4. 所有的葉子節(jié)點(diǎn)都位于同一層
5. 假設(shè)每個(gè)非終端節(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息，其中：
   • Ki (i=1...n)為關(guān)鍵字，且關(guān)鍵字按順序升序排序 K(i-1) < Ki
   • 關(guān)鍵字的個(gè)數(shù) n 必須滿足：[ceil(m / 2) - 1] <=n <= m - 1，即任意節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)上限比它的子樹上限少一個(gè)，且對(duì)于非葉子節(jié)點(diǎn)來說任意節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)比它的指向孩子的指針個(gè)數(shù)少一個(gè)
   • 非葉子節(jié)點(diǎn)的指針：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é)點(diǎn)最左子節(jié)點(diǎn)里關(guān)鍵字的值均小于該節(jié)點(diǎn)最左關(guān)鍵字的值
②：某節(jié)點(diǎn)最右子節(jié)點(diǎn)里關(guān)鍵字的值均大于該節(jié)點(diǎn)里所有關(guān)鍵字的值
③：某節(jié)點(diǎn)除左右以外所有子節(jié)點(diǎn)里關(guān)鍵字的值大小，均位于離該子節(jié)點(diǎn)指針最近的兩個(gè)關(guān)鍵字的值之間

---

B+樹

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

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

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

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

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

---

Hash以及BitMap

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

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

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

BitMap：

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

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

---

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

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

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

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

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

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

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

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

InnoDB與MyISAM引擎的檢索流程對(duì)比：

---

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

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

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

1. 最左前綴匹配原則，非常重要的原則，mysql會(huì)一直向右匹配直到遇到范圍查詢(>、<、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)化器會(huì)幫你優(yōu)化成索引可以識(shí)別的形式

我們來做個(gè)實(shí)驗(yàn)，驗(yàn)證下最左匹配原則。建表sql如下，該表中有一個(gè)聯(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字段時(shí)，會(huì)使用索引查詢：

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

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

參考文章：

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

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

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

---

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

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

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

本文題目：數(shù)據(jù)庫(kù)之索引模塊
URL地址：http://chinadenli.net/article6/giscig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、搜索引擎優(yōu)化、企業(yè)網(wǎng)站制作、、網(wǎng)站營(yíng)銷、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)