前言
你知道索引長什么樣嗎？
當磁盤剩余空間較小時，為什么我們加了索引會導致磁盤空間不足？
為什么多加了幾個索引，mysql 插入和刪除的效率反而下降了呢？
帶著這些問題，我們開始今天的話題。
什么是索引？
索引（Index）是幫助數(shù)據庫系統(tǒng)高效獲取數(shù)據的數(shù)據結構，數(shù)據庫索引本質上是以增加額外的寫操作與用于維護索引數(shù)據結構的存儲空間為代價的用于提升數(shù)據庫中數(shù)據檢索效率的數(shù)據結構。
總結一下就是，索引就是數(shù)據結構??！一種為了提升檢索效率的數(shù)據結構。
常見的數(shù)據庫的索引有：hash 表、B+樹等。
那索引物理上是怎么表現(xiàn)的呢？其實我們上一篇《mysql的數(shù)據到底是怎么存的（下）|mysql系列（5）》中講到：MySQL 的存儲結構分為 5 級：表空間、段、簇、頁、行。創(chuàng)建一個索引就會創(chuàng)建兩個段：一個數(shù)據段、一個索引段。
InnDB的索引為什么是B+樹？
二叉樹的查找效率也非常高，比如平衡二叉樹，我們在數(shù)據結構和算法中經常會用到二叉樹的思想來解決問題，我們都知道m(xù)ysql用的是B+樹，那么為什么InnDB 不用二叉樹呢？
因為平衡二叉樹這種結構在內存里面的查找效率是比較快的。但是
索引是存在于索引文件中，是存在于磁盤中的。因為索引通常是很大的，因此無法一次將全部索引加載到內存當中，因此每次只能從磁盤中讀取一個磁盤頁的數(shù)據到內存中。而這個磁盤的讀取的速度較內存中的讀取速度而言是差了好幾個級別。
因為二叉樹序列化到磁盤的時候，其物理實現(xiàn)是數(shù)組，具體可以參考
《一文搞定二叉樹—由二叉樹到貪心算法》
然后由于在邏輯結構上相近的節(jié)點在物理結構上可能會差很遠。因此，每次讀取的磁盤頁的數(shù)據中有許多是用不上的。因此，查找過程中要進行許多次的磁盤讀取操作。
二叉樹做索引有什么問題？
二叉樹應用在磁盤這類的搜索那么會有以下幾個問題:
- 數(shù)據非常大時, 樹高度會很高, 造成磁盤io掃描次數(shù)很高
- 一個節(jié)點只是存放一個數(shù)據, 數(shù)據與數(shù)據之間在物理內存相隔甚遠, 磁盤掃描需要頻繁轉動
- 需要頻繁的從磁盤讀數(shù)據到內存中, 即使操作系統(tǒng)有預讀, 但是帶出來的大多是暫時用不上的無用數(shù)據, 造成浪費
這里我們復習一下幾個知識點：
磁盤IO時間：
- 磁盤IO時間 = 尋道 + 磁盤旋轉 + 數(shù)據傳輸時間
機械硬盤的連續(xù)讀寫和隨機讀寫的性能差異：
- 順序訪問：內存訪問速度是硬盤訪問速度的6~7倍（kafka的特點，以后有機會的話再講一講）
- 隨機訪問：內存訪問速度就要比硬盤訪問速度快上10萬倍以上隨機讀寫時，磁頭需要不停的移動，時間都浪費在了磁頭尋址上。而在實際的磁盤存儲里，是很少順序存儲的，因為這樣的維護成本會很高。
局部性原理與磁盤預讀：
由于存儲介質的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費，磁盤的存取速度往往是主存的幾百分分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據放入內存。這樣做的理論依據是計算機科學中著名的局部性原理：
當一個數(shù)據被用到時，其附近的數(shù)據也通常會馬上被使用。
程序運行期間所需要的數(shù)據通常比較集中。
由于磁盤順序讀取的效率很高（不需要尋道時間，只需很少的旋轉時間），因此對于具有局部性的程序來說，預讀可以提高I/O效率。
總結一句話：由于磁盤的存儲及訪問的特性及二叉樹的物理存儲方式導致二叉樹在磁盤上的查詢速度很慢，不適合做索引。
B+樹的引入
鑒于以上幾個問題, 有以下幾點需要優(yōu)化的:
- 減少磁盤io掃描次數(shù)。
- 減少磁盤io轉動頻率。
- 利用好操作系統(tǒng)的預讀, 局部性原理。
B樹是為了充分利用磁盤預讀功能來而創(chuàng)建的一種數(shù)據結構，也就是說B樹就是為了作為索引才被發(fā)明出來的的。
B+ 樹的特點
- b+樹擁有b樹的所有優(yōu)點, 并且b+樹的非葉子節(jié)點不存放數(shù)據, 而是單單存放索引, 只有在葉子節(jié)點存放索引+數(shù)據, 并且葉子節(jié)點通過前后指針構成雙向鏈表的結構, 因此通過樹結構定位到索引后, 可以通葉子節(jié)點的鏈表指針很快的直接遍歷得到范圍查詢的結果 這樣更好的利用了順序io比隨機io性能更高的優(yōu)化. 這個特點是b樹不具備的.
- b+樹是innodb的底層數(shù)據結構, 通過N叉樹, 節(jié)點頁, 葉子節(jié)點鏈表串起來, 避免了過多的磁盤io掃描, 轉動次數(shù), 并且利用了操作系統(tǒng)的預讀和局部性原理, 更支持了范圍查詢的功能.
B+ 樹的優(yōu)點
- B樹/B+樹與紅黑樹、平衡二叉樹等二叉樹相比，最大的優(yōu)勢在于樹高更小。
- Innodb中每個節(jié)點使用一個頁(page)，頁的大小為16KB，其中元數(shù)據只占大約128字節(jié)左右(包括文件管理頭信息、頁面頭信息等等)，大多數(shù)空間都用來存儲數(shù)據。
- 對于一顆3層B+樹，第一層(根節(jié)點)有1個頁面，可以存儲1000條記錄；第二層有1000個頁面，可以存儲1000*1000條記錄；第三層(葉節(jié)點)有1000*1000個頁面，每個頁面可以存儲100條記錄，因此可以存儲1000*1000*100條記錄，即1億條。而對于二叉樹，存儲1億條記錄則需要26層左右。
總結一下
現(xiàn)在我們可以回答開頭的幾個問題了。
InnoDB 就是一個B+樹的數(shù)據結構。
每加一個索引就會生成兩個文件，所以當服務器磁盤空間少時加了索引會導致磁盤空間不足。
索引多的話，每次添加刪除數(shù)據都會維護多個文件，效率反而降低。
