【63期】談?wù)凪ySQL 索引，B+樹原理，以及建索引的幾大原則（MySQL面試第六彈）

程序員的成長(zhǎng)之路

互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享?

閱讀本文大概需要 5 分鐘。

來(lái)自：blog.csdn.net/u013142781/article/details/51706790

MYSQL一直了解得都不多，之前寫sql準(zhǔn)備提交生產(chǎn)環(huán)境之前的時(shí)候，老員工幫我檢查了下sql，讓修改了一下存儲(chǔ)引擎，當(dāng)時(shí)我使用的是Myisam，后面改成InnoDB了。為什么要改成這樣，之前都沒(méi)有聽過(guò)存儲(chǔ)引擎，于是網(wǎng)上查了一下。

事實(shí)上使用不同的存儲(chǔ)引擎也是有很大區(qū)別的，下面猿友們可以了解一下。

一、存儲(chǔ)引擎的比較

注：上面提到的B樹索引并沒(méi)有指出是B-Tree和B+Tree索引，但是B-樹和B+樹的定義是有區(qū)別的。

在 MySQL 中，主要有四種類型的索引，分別為：B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。

B-Tree 索引是 MySQL 數(shù)據(jù)庫(kù)中使用最為頻繁的索引類型，除了 Archive 存儲(chǔ)引擎之外的其他所有的存儲(chǔ)引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引，而且只支持索引單個(gè) AUTO_INCREMENT 列。

不僅僅在 MySQL 中是如此，實(shí)際上在其他的很多數(shù)據(jù)庫(kù)管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因?yàn)?B-Tree 索引的存儲(chǔ)結(jié)構(gòu)在數(shù)據(jù)庫(kù)的數(shù)據(jù)檢索中有非常優(yōu)異的表現(xiàn)。

一般來(lái)說(shuō)， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來(lái)存儲(chǔ)的，也就是所有實(shí)際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node(葉子節(jié)點(diǎn)) ，而且到任何一個(gè) Leaf Node 的最短路徑的長(zhǎng)度都是完全相同的，所以我們大家都稱之為 B-Tree 索引。

當(dāng)然，可能各種數(shù)據(jù)庫(kù)（或 MySQL 的各種存儲(chǔ)引擎）在存放自己的 B-Tree 索引的時(shí)候會(huì)對(duì)存儲(chǔ)結(jié)構(gòu)稍作改造。如 Innodb 存儲(chǔ)引擎的 B-Tree 索引實(shí)際使用的存儲(chǔ)結(jié)構(gòu)實(shí)際上是 B+Tree，也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造，在每一個(gè)Leaf Node 上面出了存放索引鍵的相關(guān)信息之外，還存儲(chǔ)了指向與該 Leaf Node 相鄰的后一個(gè) LeafNode 的指針信息（增加了順序訪問(wèn)指針），這主要是為了加快檢索多個(gè)相鄰 Leaf Node 的效率考慮。

InnoDB是Mysql的默認(rèn)存儲(chǔ)引擎(Mysql5.5.5之前是MyISAM）

可能對(duì)于沒(méi)有了解過(guò)索引的猿友這樣看這篇文章十分吃力，這類猿友有必要先對(duì)Mysql索引有個(gè)大體的了解。

接下來(lái)我們先看看B-樹、B+樹的概念。弄清楚，為什么加了索引查詢速度會(huì)加快？

二、B-樹、B+樹概念

B樹

即二叉搜索樹：

1. 所有非葉子結(jié)點(diǎn)至多擁有兩個(gè)兒子（Left和Right）；

2. 所有結(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字；

3. 非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹；

如：

B-樹

是一種多路搜索樹（并不是二叉的）：

1. 定義任意非葉子結(jié)點(diǎn)最多只有M個(gè)兒子；且M>2；

2. 根結(jié)點(diǎn)的兒子數(shù)為[2, M]；

3. 除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為[M/2, M]；

4. 每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1個(gè)關(guān)鍵字；（至少2個(gè)關(guān)鍵字）

5. 非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)=指向兒子的指針個(gè)數(shù)-1；

6. 非葉子結(jié)點(diǎn)的關(guān)鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7. 非葉子結(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])的子樹；

8. 所有葉子結(jié)點(diǎn)位于同一層；

如：（M=3）

B-樹的搜索，從根結(jié)點(diǎn)開始，對(duì)結(jié)點(diǎn)內(nèi)的關(guān)鍵字（有序）序列進(jìn)行二分查找，如果命中則結(jié)束，否則進(jìn)入查詢關(guān)鍵字所屬范圍的兒子結(jié)點(diǎn)；重復(fù)，直到所對(duì)應(yīng)的兒子指針為空，或已經(jīng)是葉子結(jié)點(diǎn)；

B-樹的特性：

1. 關(guān)鍵字集合分布在整顆樹中；

2. 任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)結(jié)點(diǎn)中；

3. 搜索有可能在非葉子結(jié)點(diǎn)結(jié)束；

4. 其搜索性能等價(jià)于在關(guān)鍵字全集內(nèi)做一次二分查找；

5. 自動(dòng)層次控制；

由于限制了除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)，至少含有M/2個(gè)兒子，確保了結(jié)點(diǎn)的至少利用率。

所以B-樹的性能總是等價(jià)于二分查找（與M值無(wú)關(guān)），也就沒(méi)有B樹平衡的問(wèn)題；

由于M/2的限制，在插入結(jié)點(diǎn)時(shí)，如果結(jié)點(diǎn)已滿，需要將結(jié)點(diǎn)分裂為兩個(gè)各占M/2的結(jié)點(diǎn)；刪除結(jié)點(diǎn)時(shí)，需將兩個(gè)不足M/2的兄弟結(jié)點(diǎn)合并；

B+樹

B+樹是B-樹的變體，也是一種多路搜索樹：

1. 其定義基本與B-樹同，除了：

2. 非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同；

3. 非葉子結(jié)點(diǎn)的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）；

4. 為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針；

5. 所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)；

如：（M=3）

B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中），其性能也等價(jià)于在關(guān)鍵字全集做一次二分查找；

B+的特性：

1. 所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點(diǎn)的鏈表中（稠密索引），且鏈表中的關(guān)鍵字恰好是有序的；

2. 不可能在非葉子結(jié)點(diǎn)命中；

3. 非葉子結(jié)點(diǎn)相當(dāng)于是葉子結(jié)點(diǎn)的索引（稀疏索引），葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；

4. 更適合文件索引系統(tǒng)；

三、建索引的幾大原則

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í)別的形式

3.盡量選擇區(qū)分度高的列作為索引,區(qū)分度的公式是count(distinct col)/count(*)，表示字段不重復(fù)的比例，比例越大我們掃描的記錄數(shù)越少，唯一鍵的區(qū)分度是1，而一些狀態(tài)、性別字段可能在大數(shù)據(jù)面前區(qū)分度就是0，那可能有人會(huì)問(wèn)，這個(gè)比例有什么經(jīng)驗(yàn)值嗎？使用場(chǎng)景不同，這個(gè)值也很難確定，一般需要join的字段我們都要求是0.1以上，即平均1條掃描10條記錄

4.索引列不能參與計(jì)算，保持列“干凈”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很簡(jiǎn)單，b+樹中存的都是數(shù)據(jù)表中的字段值，但進(jìn)行檢索時(shí)，需要把所有元素都應(yīng)用函數(shù)才能比較，顯然成本太大。所以語(yǔ)句應(yīng)該寫成create_time = unix_timestamp(’2014-05-29’);

5.盡量的擴(kuò)展索引，不要新建索引。比如表中已經(jīng)有a的索引，現(xiàn)在要加(a,b)的索引，那么只需要修改原來(lái)的索引即可。

推薦閱讀：

【62期】解釋一下MySQL中內(nèi)連接，外連接等的區(qū)別（MySQL面試第五彈）

【61期】MySQL行鎖和表鎖的含義及區(qū)別（MySQL面試第四彈）

【60期】事務(wù)隔離級(jí)別中的可重復(fù)讀能防幻讀嗎?（MySQL面試第三彈）

5T技術(shù)資源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，單片機(jī)，樹莓派，等等。在公眾號(hào)內(nèi)回復(fù)「2048」，即可免費(fèi)獲取??！

微信掃描二維碼，關(guān)注我的公眾號(hào)

朕已閱?