MySQL：從B樹到B+樹到索引再到存儲(chǔ)引擎

索引其實(shí)是一種數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)庫中，讀寫的比例是在10：1，所以如果每一次查找都全表查找的話，效率將會(huì)變的十分的低下。所以，本文將會(huì)按照題目，按部就班地講解MySql的索引。

##B樹和B+樹 B樹和B+樹算是數(shù)據(jù)結(jié)構(gòu)中出現(xiàn)頻率十分高的模型了，在筆者之前的幾篇博客，有對二叉查找樹和二叉平衡樹進(jìn)行過講解和代碼分析，但是那些都是在程序中使用比較多的樹，在數(shù)據(jù)庫中，數(shù)據(jù)量相對較大，多路查找樹顯然更加適合數(shù)據(jù)庫的應(yīng)用場景，接下來我們就介紹這兩類多路查找樹，畢竟作為程序員，心里沒點(diǎn)B樹怎么能行呢？

B樹：B樹就是B-樹，他有著如下的特性：

• B樹不同于二叉樹，他們的一個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)關(guān)鍵字和多個(gè)子樹指針，這也是B+樹的特點(diǎn)；
• 一個(gè)m階的B樹要求除了根節(jié)點(diǎn)以外，所有的非葉子子節(jié)點(diǎn)必須要有[m/2,m]個(gè)子樹；
• 根節(jié)點(diǎn)必須只能有兩個(gè)子樹，當(dāng)然，如果只有根節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的情況存在；
• B樹是一個(gè)查找二叉樹，這點(diǎn)和二叉查找樹很像，他都是越靠前的子樹越小，并且，同一個(gè)節(jié)點(diǎn)內(nèi)，關(guān)鍵字按照大小排序；
• B樹的一個(gè)節(jié)點(diǎn)要求子樹的個(gè)數(shù)等于關(guān)鍵字的個(gè)數(shù)+1；

好了，話不多說，看看B樹的模型吧：

由于B樹將所有的查找關(guān)鍵字都放在節(jié)點(diǎn)中，所以查找方式和二叉查找十分相像，比如說查找E:

先通過根節(jié)點(diǎn)找到了左子樹，再順序地遍歷左子樹，發(fā)現(xiàn)E在F和J的中間，于是查找葉子節(jié)點(diǎn)，順序遍歷關(guān)鍵字以后就可以返回E了，如果未能查到E，則表示沒有找到。

B+樹

人人都喜歡plus，B+樹就是這么一個(gè)plus，后頭所講解的索引，就是用的B+樹，我們先來看看他的特性吧：

• B+樹將所有的查找結(jié)果放在葉子節(jié)點(diǎn)中，這也就意味著查找B+樹，就必須到葉子節(jié)點(diǎn)才能返回結(jié)果；
• B+樹每一個(gè)節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)和子樹指針個(gè)數(shù)相同；
• B+樹的非葉子節(jié)點(diǎn)的每一個(gè)關(guān)鍵字對應(yīng)一個(gè)指針，而關(guān)鍵字則是子樹的最大，或者最小值；

看看模型吧：

他的查找方式也是簡單粗暴的，和B樹十分像，只不過他會(huì)在葉子節(jié)點(diǎn)中找到目標(biāo)，比如我們找兔：

第一步比馬小，就會(huì)查找他的子樹，第二部比龍小，就會(huì)查找他的子樹，最后在葉子節(jié)點(diǎn)中的關(guān)鍵字命中目標(biāo)。

那么MySql是如何利用這數(shù)據(jù)結(jié)構(gòu)的呢？

MySql中的兩種常見存儲(chǔ)引擎

MySql當(dāng)然不止兩種搜索引擎了，但是本次我們說的B+樹索引，為接下來這兩種存儲(chǔ)引擎所用，一個(gè)是Innodb，一個(gè)Myisam。（搜索公眾號(hào)Java知音，回復(fù)“2021”，送你一份Java面試題寶典）

Innodb存儲(chǔ)引擎

Innodb使用的是B+樹，他存在有一個(gè)主鍵索引和輔助索引兩種索引，主鍵索引是在生成主鍵時(shí)就有的索引，他的葉子節(jié)點(diǎn)中存放的就是數(shù)據(jù)行，所以又稱之為聚集索引。

而另一類索引，輔助索引，就是我們?nèi)藶樾陆ǖ乃饕娜~子節(jié)點(diǎn)中存放的是主鍵，當(dāng)我們通過輔助索引查找到主鍵之后，再通過查找的主鍵去查找主鍵索引，我們看看兩種索引的結(jié)構(gòu)吧：

MyIsam存儲(chǔ)引擎

很顯然，MyIsam不可能再會(huì)用聚集索引了，雖然他用的是B+樹，但是他的主鍵索引和輔助索引沒有任何區(qū)別，都是在葉子中存儲(chǔ)數(shù)據(jù)行的物理地址，這也使得他的讀性能更高，我們來看他的模型吧：

區(qū)別

1、innodb支持事務(wù)，且默認(rèn)是Autocommit，所以每一條SQL語句都會(huì)封裝成一個(gè)事務(wù)，如果執(zhí)行多條事務(wù)，最好加上begin和commit。MyIsam不支持事務(wù)，也就無法回滾；

2、另外Innodb支持行鎖，MyIsam進(jìn)行寫操作會(huì)全表上鎖，所以MyIsam的寫操作性能會(huì)差些；

3、所以，在查詢較多的表中，使用MyIsam較優(yōu)，寫比較多的表，使用Innodb；

拓展--復(fù)合索引

我們都知道我們可以對一個(gè)列創(chuàng)建一個(gè)索引，但是什么是復(fù)合索引呢？

創(chuàng)建：

create table test(
a int,
b int,
c int,
KEY a(a,b,c)
);

通過以上代碼我們就可以創(chuàng)建一個(gè)a、b、c三個(gè)字段的復(fù)合索引了，相對于維護(hù)三個(gè)索引，維護(hù)一個(gè)復(fù)合索引的開銷肯定是更低的。

但是復(fù)合索引需要滿足一個(gè)最左匹配原則，也就是他會(huì)依次查找a、b、c三個(gè)字段，當(dāng)左邊的字段未作為判斷條件時(shí)，就不會(huì)再去執(zhí)行接下來的索引了，測試如下：

EXPLAIN DELETE from test
where  a=1 and c= 3 and b =2 

EXPLAIN DELETE from test
where  a=1 and c= 3