前言

你知道索引長什么樣嗎？

當(dāng)磁盤剩余空間較小時(shí)，為什么我們加了索引會(huì)導(dǎo)致磁盤空間不足？

為什么多加了幾個(gè)索引，mysql 插入和刪除的效率反而下降了呢？

帶著這些問題，我們開始今天的話題。

什么是索引？

索引（Index）是幫助數(shù)據(jù)庫系統(tǒng)高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)庫索引本質(zhì)上是以增加額外的寫操作與用于維護(hù)索引數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間為代價(jià)的用于提升數(shù)據(jù)庫中數(shù)據(jù)檢索效率的數(shù)據(jù)結(jié)構(gòu)。

總結(jié)一下就是，索引就是數(shù)據(jù)結(jié)構(gòu)！！一種為了提升檢索效率的數(shù)據(jù)結(jié)構(gòu)。

常見的數(shù)據(jù)庫的索引有：hash 表、B+樹等。

那索引物理上是怎么表現(xiàn)的呢？其實(shí)我們上一篇《mysql的數(shù)據(jù)到底是怎么存的（下）|mysql系列（5）》中講到：MySQL 的存儲(chǔ)結(jié)構(gòu)分為 5 級(jí)：表空間、段、簇、頁、行。創(chuàng)建一個(gè)索引就會(huì)創(chuàng)建兩個(gè)段：一個(gè)數(shù)據(jù)段、一個(gè)索引段。

InnDB的索引為什么是B+樹？

二叉樹的查找效率也非常高，比如平衡二叉樹，我們?cè)跀?shù)據(jù)結(jié)構(gòu)和算法中經(jīng)常會(huì)用到二叉樹的思想來解決問題，我們都知道m(xù)ysql用的是B+樹，那么為什么InnDB 不用二叉樹呢？

因?yàn)槠胶舛鏄溥@種結(jié)構(gòu)在內(nèi)存里面的查找效率是比較快的。但是

索引是存在于索引文件中，是存在于磁盤中的。因?yàn)樗饕ǔＪ呛艽蟮模虼藷o法一次將全部索引加載到內(nèi)存當(dāng)中，因此每次只能從磁盤中讀取一個(gè)磁盤頁的數(shù)據(jù)到內(nèi)存中。而這個(gè)磁盤的讀取的速度較內(nèi)存中的讀取速度而言是差了好幾個(gè)級(jí)別。

因?yàn)槎鏄湫蛄谢酱疟P的時(shí)候，其物理實(shí)現(xiàn)是數(shù)組，具體可以參考

《一文搞定二叉樹—由二叉樹到貪心算法》

然后由于在邏輯結(jié)構(gòu)上相近的節(jié)點(diǎn)在物理結(jié)構(gòu)上可能會(huì)差很遠(yuǎn)。因此，每次讀取的磁盤頁的數(shù)據(jù)中有許多是用不上的。因此，查找過程中要進(jìn)行許多次的磁盤讀取操作。

二叉樹做索引有什么問題？

二叉樹應(yīng)用在磁盤這類的搜索那么會(huì)有以下幾個(gè)問題:

• 數(shù)據(jù)非常大時(shí), 樹高度會(huì)很高, 造成磁盤io掃描次數(shù)很高
• 一個(gè)節(jié)點(diǎn)只是存放一個(gè)數(shù)據(jù), 數(shù)據(jù)與數(shù)據(jù)之間在物理內(nèi)存相隔甚遠(yuǎn), 磁盤掃描需要頻繁轉(zhuǎn)動(dòng)
• 需要頻繁的從磁盤讀數(shù)據(jù)到內(nèi)存中, 即使操作系統(tǒng)有預(yù)讀, 但是帶出來的大多是暫時(shí)用不上的無用數(shù)據(jù), 造成浪費(fèi)

這里我們復(fù)習(xí)一下幾個(gè)知識(shí)點(diǎn)：

磁盤IO時(shí)間：

• 磁盤IO時(shí)間 = 尋道 + 磁盤旋轉(zhuǎn) + 數(shù)據(jù)傳輸時(shí)間

機(jī)械硬盤的連續(xù)讀寫和隨機(jī)讀寫的性能差異：

• 順序訪問：內(nèi)存訪問速度是硬盤訪問速度的6~7倍（kafka的特點(diǎn)，以后有機(jī)會(huì)的話再講一講）
• 隨機(jī)訪問：內(nèi)存訪問速度就要比硬盤訪問速度快上10萬倍以上隨機(jī)讀寫時(shí)，磁頭需要不停的移動(dòng)，時(shí)間都浪費(fèi)在了磁頭尋址上。而在實(shí)際的磁盤存儲(chǔ)里，是很少順序存儲(chǔ)的，因?yàn)檫@樣的維護(hù)成本會(huì)很高。

局部性原理與磁盤預(yù)讀：

由于存儲(chǔ)介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機(jī)械運(yùn)動(dòng)耗費(fèi)，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達(dá)到這個(gè)目的，磁盤往往不是嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀，即使只需要一個(gè)字節(jié)，磁盤也會(huì)從這個(gè)位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中著名的局部性原理：

當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用。

程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中。

由于磁盤順序讀取的效率很高（不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間），因此對(duì)于具有局部性的程序來說，預(yù)讀可以提高I/O效率。

總結(jié)一句話：由于磁盤的存儲(chǔ)及訪問的特性及二叉樹的物理存儲(chǔ)方式導(dǎo)致二叉樹在磁盤上的查詢速度很慢，不適合做索引。

B+樹的引入

鑒于以上幾個(gè)問題, 有以下幾點(diǎn)需要優(yōu)化的:

• 減少磁盤io掃描次數(shù)。
• 減少磁盤io轉(zhuǎn)動(dòng)頻率。
• 利用好操作系統(tǒng)的預(yù)讀, 局部性原理。

B樹是為了充分利用磁盤預(yù)讀功能來而創(chuàng)建的一種數(shù)據(jù)結(jié)構(gòu)，也就是說B樹就是為了作為索引才被發(fā)明出來的的。

B+ 樹的特點(diǎn)

• b+樹擁有b樹的所有優(yōu)點(diǎn), 并且b+樹的非葉子節(jié)點(diǎn)不存放數(shù)據(jù), 而是單單存放索引, 只有在葉子節(jié)點(diǎn)存放索引+數(shù)據(jù), 并且葉子節(jié)點(diǎn)通過前后指針構(gòu)成雙向鏈表的結(jié)構(gòu), 因此通過樹結(jié)構(gòu)定位到索引后, 可以通葉子節(jié)點(diǎn)的鏈表指針很快的直接遍歷得到范圍查詢的結(jié)果 這樣更好的利用了順序io比隨機(jī)io性能更高的優(yōu)化. 這個(gè)特點(diǎn)是b樹不具備的.
• b+樹是innodb的底層數(shù)據(jù)結(jié)構(gòu), 通過N叉樹, 節(jié)點(diǎn)頁, 葉子節(jié)點(diǎn)鏈表串起來, 避免了過多的磁盤io掃描, 轉(zhuǎn)動(dòng)次數(shù), 并且利用了操作系統(tǒng)的預(yù)讀和局部性原理, 更支持了范圍查詢的功能.

B+ 樹的優(yōu)點(diǎn)

• B樹/B+樹與紅黑樹、平衡二叉樹等二叉樹相比，最大的優(yōu)勢在于樹高更小。
• Innodb中每個(gè)節(jié)點(diǎn)使用一個(gè)頁(page)，頁的大小為16KB，其中元數(shù)據(jù)只占大約128字節(jié)左右(包括文件管理頭信息、頁面頭信息等等)，大多數(shù)空間都用來存儲(chǔ)數(shù)據(jù)。
• 對(duì)于一顆3層B+樹，第一層(根節(jié)點(diǎn))有1個(gè)頁面，可以存儲(chǔ)1000條記錄；第二層有1000個(gè)頁面，可以存儲(chǔ)1000*1000條記錄；第三層(葉節(jié)點(diǎn))有1000*1000個(gè)頁面，每個(gè)頁面可以存儲(chǔ)100條記錄，因此可以存儲(chǔ)1000*1000*100條記錄，即1億條。而對(duì)于二叉樹，存儲(chǔ)1億條記錄則需要26層左右。

總結(jié)一下

現(xiàn)在我們可以回答開頭的幾個(gè)問題了。

InnoDB 就是一個(gè)B+樹的數(shù)據(jù)結(jié)構(gòu)。

每加一個(gè)索引就會(huì)生成兩個(gè)文件，所以當(dāng)服務(wù)器磁盤空間少時(shí)加了索引會(huì)導(dǎo)致磁盤空間不足。

索引多的話，每次添加刪除數(shù)據(jù)都會(huì)維護(hù)多個(gè)文件，效率反而降低。