面試時(shí)候經(jīng)常會(huì)被問(wèn)到mysql的索引結(jié)構(gòu)，B+樹相較二叉樹涛菠，紅黑樹的優(yōu)勢(shì)等問(wèn)題莉御，接下來(lái)就分析下這些問(wèn)題。

二叉查找樹(BST)

首先俗冻，讓我們先看一張圖：

1

從圖中可以看到礁叔，我們?yōu)?user 表（用戶信息表）建立了一個(gè)二叉查找樹的索引。

圖中的圓為二叉查找樹的節(jié)點(diǎn)迄薄，節(jié)點(diǎn)中存儲(chǔ)了鍵（key）和數(shù)據(jù)（data）琅关。鍵對(duì)應(yīng) user 表中的 id，數(shù)據(jù)對(duì)應(yīng) user 表中的行數(shù)據(jù)讥蔽。

二叉查找樹的特點(diǎn)就是任何節(jié)點(diǎn)的左子節(jié)點(diǎn)的鍵值都小于當(dāng)前節(jié)點(diǎn)的鍵值涣易，右子節(jié)點(diǎn)的鍵值都大于當(dāng)前節(jié)點(diǎn)的鍵值。頂端的節(jié)點(diǎn)我們稱為根節(jié)點(diǎn)冶伞，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)我們稱之為葉節(jié)點(diǎn)新症。

如果我們需要查找 id=12 的用戶信息，利用我們創(chuàng)建的二叉查找樹索引响禽，查找流程如下：

• 將根節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)徒爹，把 12 與當(dāng)前節(jié)點(diǎn)的鍵值 10 比較荚醒，12 大于 10，接下來(lái)我們把當(dāng)前節(jié)點(diǎn)>的右子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)隆嗅。
• 繼續(xù)把 12 和當(dāng)前節(jié)點(diǎn)的鍵值 13 比較腌且，發(fā)現(xiàn) 12 小于 13，把當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)榛瓮。
• 把 12 和當(dāng)前節(jié)點(diǎn)的鍵值 12 對(duì)比铺董，12 等于 12，滿足條件禀晓，我們從當(dāng)前節(jié)點(diǎn)中取出 data精续，即 id=12，name=xm粹懒。

利用二叉查找樹我們只需要 3 次即可找到匹配的數(shù)據(jù)重付。如果在表中一條條的查找的話，我們需要 6 次才能找到凫乖。

平衡二叉樹

上面我們講解了利用二叉查找樹可以快速的找到數(shù)據(jù)确垫。但是，如果上面的二叉查找樹是這樣的構(gòu)造：

2

這個(gè)時(shí)候可以看到我們的二叉查找樹變成了一個(gè)鏈表帽芽。如果我們需要查找 id=17 的用戶信息删掀，我們需要查找 7 次，也就相當(dāng)于全表掃描了导街。 導(dǎo)致這個(gè)現(xiàn)象的原因其實(shí)是二叉查找樹變得不平衡了披泪，也就是高度太高了，從而導(dǎo)致查找效率的不穩(wěn)定搬瑰。為了解決這個(gè)問(wèn)題款票，我們需要保證二叉查找樹一直保持平衡，就需要用到平衡二叉樹了泽论。 平衡二叉樹又稱 AVL 樹艾少，在滿足二叉查找樹特性的基礎(chǔ)上，要求每個(gè)節(jié)點(diǎn)的左右子樹的高度差不能超過(guò) 1翼悴。
下面是平衡二叉樹和非平衡二叉樹的對(duì)比：

3

由平衡二叉樹的構(gòu)造我們可以發(fā)現(xiàn)第一張圖中的二叉樹其實(shí)就是一棵平衡二叉樹缚够。

平衡二叉樹保證了樹的構(gòu)造是平衡的，當(dāng)我們插入或刪除數(shù)據(jù)導(dǎo)致不滿足平衡二叉樹不平衡時(shí)抄瓦，平衡二叉樹會(huì)進(jìn)行調(diào)整樹上的節(jié)點(diǎn)來(lái)保持平衡潮瓶。具體的調(diào)整方式這里就不介紹了陶冷。平衡二叉樹相比于二叉查找樹來(lái)說(shuō)钙姊，查找效率更穩(wěn)定，總體的查找速度也更快埂伦。

B樹

因?yàn)閮?nèi)存的易失性煞额。一般情況下，我們都會(huì)選擇將 user 表中的數(shù)據(jù)和索引存儲(chǔ)在磁盤這種外圍設(shè)備中。但是和內(nèi)存相比膊毁，從磁盤中讀取數(shù)據(jù)的速度會(huì)慢上百倍千倍甚至萬(wàn)倍胀莹，所以，我們應(yīng)當(dāng)盡量減少?gòu)拇疟P中讀取數(shù)據(jù)的次數(shù)婚温。另外描焰，從磁盤中讀取數(shù)據(jù)時(shí)，都是按照磁盤塊來(lái)讀取的栅螟，并不是一條一條的讀荆秦。如果我們能把盡量多的數(shù)據(jù)放進(jìn)磁盤塊中，那一次磁盤讀取操作就會(huì)讀取更多數(shù)據(jù)力图，那我們查找數(shù)據(jù)的時(shí)間也會(huì)大幅度降低步绸。如果我們用樹這種數(shù)據(jù)結(jié)構(gòu)作為索引的數(shù)據(jù)結(jié)構(gòu)，那我們每查找一次數(shù)據(jù)就需要從磁盤中讀取一個(gè)節(jié)點(diǎn)，也就是我們說(shuō)的一個(gè)磁盤塊。我們都知道平衡二叉樹可是每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)鍵值和數(shù)據(jù)的疆栏。那說(shuō)明什么快耿？說(shuō)明每個(gè)磁盤塊僅僅存儲(chǔ)一個(gè)鍵值和數(shù)據(jù)！那如果我們要存儲(chǔ)海量的數(shù)據(jù)呢棕硫？

可以想象到二叉樹的節(jié)點(diǎn)將會(huì)非常多，高度也會(huì)極其高，我們查找數(shù)據(jù)時(shí)也會(huì)進(jìn)行很多次磁盤 IO漾月，我們查找數(shù)據(jù)的效率將會(huì)極低！

4

為了解決平衡二叉樹的這個(gè)弊端胃珍，我們應(yīng)該尋找一種單個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)鍵值和數(shù)據(jù)的平衡樹梁肿。也就是我們接下來(lái)要說(shuō)的 B 樹。

B 樹（Balance Tree）即為平衡樹的意思觅彰，下圖即是一棵 B 樹：

5

圖中的 p 節(jié)點(diǎn)為指向子節(jié)點(diǎn)的指針吩蔑，二叉查找樹和平衡二叉樹其實(shí)也有，因?yàn)閳D的美觀性填抬，被省略了烛芬。

圖中的每個(gè)節(jié)點(diǎn)稱為頁(yè)，頁(yè)就是我們上面說(shuō)的磁盤塊飒责，在 MySQL 中數(shù)據(jù)讀取的基本單位都是頁(yè)赘娄，所以我們這里叫做頁(yè)更符合 MySQL 中索引的底層數(shù)據(jù)結(jié)構(gòu)。

從上圖可以看出宏蛉，B 樹相對(duì)于平衡二叉樹遣臼，每個(gè)節(jié)點(diǎn)存儲(chǔ)了更多的鍵值（key）和數(shù)據(jù)（data），并且每個(gè)節(jié)點(diǎn)擁有更多的子節(jié)點(diǎn)拾并，子節(jié)點(diǎn)的個(gè)數(shù)一般稱為階揍堰，上述圖中的 B 樹為 3 階 B 樹鹏浅，高度也會(huì)很低。

基于這個(gè)特性屏歹，B 樹查找數(shù)據(jù)讀取磁盤的次數(shù)將會(huì)很少隐砸，數(shù)據(jù)的查找效率也會(huì)比平衡二叉樹高很多。

假如我們要查找 id=28 的用戶信息蝙眶，那么我們?cè)谏蠄D B 樹中查找的流程如下：

• 先找到根節(jié)點(diǎn)也就是頁(yè) 1季希，判斷 28 在鍵值 17 和 35 之間，那么我們根據(jù)頁(yè) 1 中的指針 p2 找到頁(yè) 3幽纷。
• 將 28 和頁(yè) 3 中的鍵值相比較胖眷，28 在 26 和 30 之間，我們根據(jù)頁(yè) 3 中的指針 p2 找到頁(yè) 8霹崎。
• 將 28 和頁(yè) 8 中的鍵值相比較珊搀，發(fā)現(xiàn)有匹配的鍵值 28，鍵值 28 對(duì)應(yīng)的用戶信息為（28尾菇，bv）境析。

B+樹

B+ 樹是對(duì) B 樹的進(jìn)一步優(yōu)化。讓我們先來(lái)看下 B+ 樹的結(jié)構(gòu)圖：

6

根據(jù)上圖我們來(lái)看下 B+ 樹和 B 樹有什么不同：

1. B+ 樹非葉子節(jié)點(diǎn)上是不存儲(chǔ)數(shù)據(jù)的派诬，僅存儲(chǔ)鍵值劳淆，而 B 樹節(jié)點(diǎn)中不僅存儲(chǔ)鍵值，也會(huì)存儲(chǔ)數(shù)據(jù)默赂。
   之所以這么做是因?yàn)樵跀?shù)據(jù)庫(kù)中頁(yè)的大小是固定的沛鸵，InnoDB 中頁(yè)的默認(rèn)大小是 16KB。
   如果不存儲(chǔ)數(shù)據(jù)缆八，那么就會(huì)存儲(chǔ)更多的鍵值曲掰，相應(yīng)的樹的階數(shù)（節(jié)點(diǎn)的子節(jié)點(diǎn)樹）就會(huì)更大，樹就會(huì)更矮更胖奈辰，如此一來(lái)我們查找數(shù)據(jù)進(jìn)行磁盤的 IO 次數(shù)又會(huì)再次減少栏妖，數(shù)據(jù)查詢的效率也會(huì)更快。
   另外奖恰，B+ 樹的階數(shù)是等于鍵值的數(shù)量的吊趾，如果我們的 B+ 樹一個(gè)節(jié)點(diǎn)可以存儲(chǔ) 1000 個(gè)鍵值，那么 3 層 B+ 樹可以存儲(chǔ) 1000×1000×1000=10 億個(gè)數(shù)據(jù)瑟啃。
   一般根節(jié)點(diǎn)是常駐內(nèi)存的论泛，所以一般我們查找 10 億數(shù)據(jù)，只需要 2 次磁盤 IO蛹屿。

2. 因?yàn)?B+ 樹索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn)屁奏，而且數(shù)據(jù)是按照順序排列的。
   那么 B+ 樹使得范圍查找蜡峰，排序查找了袁，分組查找以及去重查找變得異常簡(jiǎn)單。而 B 樹因?yàn)閿?shù)據(jù)分散在各個(gè)節(jié)點(diǎn)湿颅，要實(shí)現(xiàn)這一點(diǎn)是很不容易的载绿。
   有心的讀者可能還發(fā)現(xiàn)上圖 B+ 樹中各個(gè)頁(yè)之間是通過(guò)雙向鏈表連接的，葉子節(jié)點(diǎn)中的數(shù)據(jù)是通過(guò)單向鏈表連接的油航。
   其實(shí)上面的 B 樹我們也可以對(duì)各個(gè)節(jié)點(diǎn)加上鏈表崭庸。這些不是它們之前的區(qū)別，是因?yàn)樵?MySQL 的 InnoDB 存儲(chǔ)引擎中谊囚，索引就是這樣存儲(chǔ)的怕享。
   也就是說(shuō)上圖中的 B+ 樹索引就是 InnoDB 中 B+ 樹索引真正的實(shí)現(xiàn)方式，準(zhǔn)確的說(shuō)應(yīng)該是聚集索引镰踏。

通過(guò)上圖可以看到函筋，在 InnoDB 中，我們通過(guò)數(shù)據(jù)頁(yè)之間通過(guò)雙向鏈表連接以及葉子節(jié)點(diǎn)中數(shù)據(jù)之間通過(guò)單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)奠伪。

MyISAM 中的 B+ 樹索引實(shí)現(xiàn)與 InnoDB 中的略有不同跌帐。在 MyISAM 中，B+ 樹索引的葉子節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)绊率，而是存儲(chǔ)數(shù)據(jù)的文件地址谨敛。

總結(jié)

1. 二叉查找樹(BST)：解決了排序的基本問(wèn)題，但是由于無(wú)法保證平衡滤否，可能退化為鏈表脸狸；

2. 平衡二叉樹(AVL)：通過(guò)旋轉(zhuǎn)解決了平衡的問(wèn)題，但是旋轉(zhuǎn)操作效率太低藐俺；

3. B樹：通過(guò)將二叉樹改為多路平衡查找樹炊甲，解決了樹過(guò)高的問(wèn)題；

4. B+樹：在B樹的基礎(chǔ)上欲芹，將非葉節(jié)點(diǎn)改造為不存儲(chǔ)數(shù)據(jù)的純索引節(jié)點(diǎn)蜜葱，進(jìn)一步降低了樹的高度；此外將葉節(jié)點(diǎn)使用指針連接成鏈表耀石，范圍查詢更加高效牵囤。

摘自：http://www.liuzk.com/410.html