mysql索引底層原理
參考：騰訊課堂
如有侵權，請聯繫本人立即刪除。
在騰訊課堂上了一節mysql索引底層原理的課，感覺很不錯，所以在此分享一波。
資料庫中最常見的慢查詢的優化方式是什麼？
答：加索引
為什麼加索引能優化慢查詢？
答：因為索引其實就是一種優化查詢的數據結構。比如mysql的索引就是使用B+樹來實現的，而B+樹就是一種數據結構，可以優化查詢速度。所以可以利用索引來優化慢查詢。
索引定義：優化查詢的數據結構。
我們知道，可以用來優化查詢的數據結構有哈希表，完全平衡二叉樹，B樹，B+樹。那麼為什麼我們使用最多的是B+樹呢？
首先，我們先來看哈希表。
哈希表的存儲是這樣的：比如你要存儲「小紅」這個字元串，則要先獲得hashcode，然後再計算要放入的數組下標，然後再放入。此時可能會產生哈希碰撞問題，所以常創建鏈表解決（即拉鏈法）。
這裡推薦一個數據結構可視化的網站，可能需要出國外訪問。
Open Hash Tables (Closed Addressing)
這裡就可以模擬哈希表的插入過程，然後大家就可以理解哈希索引了。
上面是我的一個使用截屏，由於我之前寫過很多關於hashmap的文章了，了解比較深，所以就不細講了。
就比如對名字建立哈希索引，然後select * from student where name="小紅"。那麼mysql就會根據「小紅」這個字元串先找到數組下標，然後定位到具體的節點，然後從節點中取出「小紅」這一行記錄所在的地址，然後再去地址中找到這行的記錄。（這是myisam的非聚族索引的情況，葉子節點存放的記錄的地址）
然後來看哈希索引的優點和缺點：
優點：就如上述描述的這樣，直接進行計算下標，直接查詢單一數據非常快。
缺點：如果是進行select * from student where age>18;這樣的範圍查詢的話，哈希索引就必須全表遍歷，獲得age數據，然後再依次進行比較，也就是相當於沒有索引了。這樣就不能優化查詢效率了。
然後再來看完全平衡二叉樹：
前面在以前的文章中隊紅黑樹和平衡二叉樹做過深入的了解，這裡就不細講他的結構了。
這裡就直接上圖理解：
AVL Trees (Balanced binary search trees)
很明顯，二叉樹這個定義的本身就限制了它，即一個節點只能有兩個子節點。所以當插入的數據非常多時，樹的深度就會非常高。樹的深度非常高的話就會影響查詢效率。所以沒有使用二叉樹來當索引的。但是，它支持範圍查詢，因為二叉樹是有序的。而且也可以提高查詢效率，還是因為它是有序的，而且高度相比其它二叉樹更平衡，通過二分法查詢即可。但是，由於存儲大量數據時高度太高，會影響效率。（後面進行詳細解釋）
然後再來看B樹：
B Trees
不知道大家對B樹的理解怎麼樣，可以自己在網址里輸入一波，我簡單介紹一下就是可以一個節點可以存儲多個節點的搜索樹。這樣就沒有了二叉樹的兩個節點的限制，同時帶有有序的特點。所以圖中有個參數：MAX.Degree,即一個節點存儲的最大節點數，這裡設置的是3，看得比較明顯。這樣的話一層就可以存儲很多的數據了。
這樣看B樹，它有二分查找可以快速定位數據的所在位置，而且每層可以存放大量數據，所以樹的高度低。感覺還是很不錯的。但是，它在進行mysql的範圍查詢時也顯示出缺陷，B樹不支持範圍查詢（或者說範圍查詢效率太低，因為比一個數據大的話，雖說肯定會在右子樹，但是上層數據和其它子樹的數據不好對比，理解B樹的結構就很好理解）
然後，再來看我們的最終大boss，B+樹
B+ Trees
我們對比一下B+樹和B樹，發現了什麼？圖中是有重複元素的，仔細一看，所有的非葉子節點都在葉子節點中出現了備份。也就是說，最下面的一層，也就是所有的葉子節點就包含了所有的數據。這就和前面的所有結構都不一樣的地方了。然後，比起B樹而言，葉子節點這層還有指向後面的指針，也就是多了指向。這就能很好地進行了範圍查詢，很好地解決了B樹的問題。這樣定位到數據後，直接在這層的指針遍歷即可。
這就是我們最經常使用的B+樹。
我們來分析一下索引遍歷的過程，先通過類似的二分原理快速地定位數據，然後取出節點中的對應的記錄地址，然後再到地址中取出對應的記錄。perfect！
經過上述的討論，我總結了一下，衡量一種mysql索引好不好有三個原則：
1.能不能快速定位到元素所在位置
2.能不能較好的進行範圍查詢
3.樹的高度是低還是高
然後，我們在來看看為啥樹的高度越高，查詢效率越低呢？
首先，我們要了解到索引數據其實相對來說還是是很大的。在實際項目場景中，存儲的可能是上億的數據，即使只是其中的部分，索引還是非常大，我們是不可能把那麼多的數據全部同時放入內存當中的。所以，這些索引也是存放在磁碟當中的。所以我們可以思考，哪種數據結構更適合從磁碟讀取數據？或者說，哪種數據結構更能提高磁碟的io效率？
如圖：這是B+樹的
先來模擬一次B+樹的讀取過程：
比如要找艾克：
1.先從磁碟中取出海獸祭司到內存（第一次磁碟io讀取），發現不是，而且艾克對應的key大于海獸祭司的，知道要找右子樹。
2.從右子樹中取出蓋倫（第二次磁碟io讀取），發現不是，發現艾克的key大於蓋倫的，所以繼續找右子樹。
3.找到了艾克。
所以里進行了兩次的磁碟io。
然後在完全平衡二叉樹中在存放，假設艾克還是在最底層，同理，可發現要進行3次磁碟io。所以，也就是樹的高度決定了磁碟io的次數，也就是直接影響了查詢效率。
上面的例子限制了B+樹的節點數，所以看起來不是很明顯，當大量數據進行存儲時，則會產生巨大的變化。你走了100公里找到了水，別人走了 1 公里就找到了水，你是不是得像別人學習一下啊？
所以，到這裡，我們可以總結出：mysql選用B+樹這種數據結構作為索引，可以提高查詢索引時的磁碟io效率，並且可以提高範圍查詢的效率，並且B+樹立的元素也是有序的。
那麼，B+樹中的一個節點存儲多少個元素比較合適呢，也就是說，一個節點要多大比較合適呢？這就是一個問題了。一大堆的擴展知識即將來襲，請做好準備。
首先，我們需要了解磁碟io的原理。
先來看機械硬碟：
然後來看機械硬碟的存儲原理：
一個磁碟由大小相同且同軸的圓形碟片組成，磁碟可以轉動(各個磁碟必須同步轉動)。在磁碟的一側有磁頭支架，磁頭支架固定了一組磁頭， 每個磁頭負責存取一個磁碟的內容。磁頭不能轉動，但是可以沿磁碟半徑方向運動(實際是斜切向運動)，每個磁頭同一時刻也必須是同軸的，即從正上方向下看，所有磁頭任何時候都是重疊的(不過目前已經有多磁頭獨立技術，可不受此限制)。
一般來說一個磁碟有一個碟片，一個碟片對應正反面兩個磁頭。這叫單碟，特點是比較穩定。現在也有一個磁碟兩個碟片，也就是四個磁頭。這叫雙碟，特點是容量比較大。
下面是磁碟片的結構圖：
碟片被劃分成一系列同心環，圓心是碟片中心，每個同心環叫做一個磁軌，所有半徑相同的磁軌組成-個柱面。磁軌被沿半徑線劃分成一個個小的段， 每個段叫做一個扇區，每個扇區是磁碟的最小存儲單元，大小一般為521位元組。
然後我們來看磁碟讀取數據的邏輯：
當需要從磁碟讀取數據時，系統會將數據邏輯地址傳給磁碟，磁碟的控制電路按照定址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數據在哪個磁軌，哪個扇區。為了讀取這個扇區的數據，需要將磁頭放到這個扇區上方，為了實現這一點,磁頭需要移動對準相應磁軌，這個過程叫做尋道，所耗費時間叫做尋道時間，然後磁碟旋轉將目標扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。
然後我們再來看固態硬碟：
固態硬碟(Solid State Drives)，用固態電子 存儲晶元陣列而製成的硬碟，由控制單元和存儲單元(FLASH晶元、DRAM晶元)組成。固態硬碟在介面的規範和定義、功能及使用方法上與普通硬碟的完全相同，在產品外形和尺寸上也完全與普通硬碟-致。
控制單元
每個SSD都有一個控制器(cotollen)將存儲單元連接到電腦，主控器可以通過若干個通道(channel) 並行操作多塊存儲單元
存儲單元
-個Flash Page由兩個或者多個Die(又稱chips組成)，這些Dies可以共享10數據匯流排和一些控制信號線。一個Die又可以分為多個Plane,而每個Plane又包含多個多個Block,每個Block又分為多個Page。以Samsung 4GBFlash為例，一個4GB的Flash Page由兩個2GB的Die組成，共享8位I/0數據匯流排和一些控制信號線。每個Die由4個Plane組成，每個Plane包含2048個Block,每個Block又包含64個4KB大小的Page
訪問SSD的原理
Host是通過LBA (Logical BlockAddress,邏輯地址塊)訪問SSD的，每個LBA代表著一個Sector (- 般為512B大小，操作系統一般以4K為 單位訪問SSD,我們把Host訪問SSD的基本單元叫用戶頁(Host Page)。而在SSD內部，SSD主控與Flash之間是Flash Page為基本單元訪問Flash的，我們稱Flash Page為物理頁(PhysicalPage)。 Host每寫入-個Host Page, SSD主控會找-個Physical Page把Host數據寫入，SSD內部同時記錄了這樣一條映射(Map) 。有了這樣-個映射關係後，下次Host需 要讀某個Host Page時，SSD就知道從Flash的哪個位置把數據讀取上來。
局部性原理與磁碟預讀
計算機科學中著名的局部性原理:當一個數據被用到時，其附近的數據也通常會馬上被使用。
所以操作系統為了提高效率，讀取數據時往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個位元組，操作系統也會從這個位置開始，順序向後讀取一定長度的數據放入內存。這裡的-定長度叫做頁，也就是操作系統操作磁碟時的基本單位。一般操作系統中 一頁的大小是4Kb。
從上面的原理我們也能知道，固態硬碟比機械硬碟快的最根本最簡單的原因就是:固態硬碟使用的電路進行讀寫，而機械硬碟使用的機械運動。
其實不管是機械硬碟還是固態硬碟都是存儲介質,真正控制讀寫的是操作系統。這部分屬於計算機原理和操作系統方面的知識，感覺理解一下還是很有必要的。如果還看過我在操作系統專欄中寫的內存管理方面的請求段頁式存儲，相信大家會更有所感悟。
所以，回到我們的問題，B+樹中一個節點到底存多少個元素合適?，其實也可以換個角度來思考B+樹中一個節點到底多大合適?
答案是: B+樹中一個節點為一頁或頁的倍數最為合適。因為如果一個節點的大小小於1頁，那麼讀取這個節點的時候其實也會讀出1頁，造成資源的浪費;如果一個節點的大小大於1頁，比如1.2頁，那麼讀取這個節點的時候會讀出2頁，也會造成資源的浪費;所以為了不造成浪費，所以最後把一個節點的大小控制在1頁、2頁、3頁、4頁等倍數頁大小最為合適。
那麼，Mysql中B+樹的一個節點大小為多大呢?
這個問題的答案是「1頁"」，這裡說的頁"是Mysq自定義的單位(其實和操作系統類似)，Mysql的nnodb引擎中一頁的默認大小是16k (如果操作系統中-頁大小是4k，那麼Mysql中1 頁=操作系統中4頁)，可以使用命令SHOW GLOBAL STATUS like Innodb_ page size;查看。 並且還可以告訴你的是，一個節點為1頁就夠了。
為什麼一個節點為一頁（16kb）就夠了呢？
先來看看mylsam和innodb使用B+樹的情況：
通常我們認為B+樹的非葉子節點不存儲數據，只有葉子節點才存儲數據。而B樹的非葉子節點和葉子節點都會存儲數據，這會導致非葉子節點存儲的索引值更少，樹的高度相對會比B+樹高，平均的io效率會比較低，所以使用B+樹作為索引的數據結構，再加上B+樹的葉子節點之間會有指針相連，便於範圍查詢。上圖的data區域兩個存儲引擎會有所不同，也就是聚族和非聚族索引的區別。後面詳細講解。
（這裡說一下我對這裡的為啥B樹的高度相對B+樹高的理解：就如上圖所見，一個節點指的是
這才是一個節點，而不是單純的15，或者加上旁邊的一個指針。這樣的話，前面已知一個節點是16kb大小，那麼在這固定大小中，B樹的非葉子節點還要存儲數據，而B+樹只存儲值和指針。具體一點就是，假設數據大小2kb，值大小1kb,指針大小1kb。那麼B樹里只能有4個值，而B+樹里則有8個值，這樣的話，整個索引存儲相同數量的值的話，B+樹明顯就比B樹低，這樣就提高了磁碟的io效率）
前面我們提到數據區域存儲的東西，現在來進行詳細解釋：
myisam中，葉子節點的數據區域存儲的是數據記錄的地址。這也叫非聚族索引。
下面是主鍵索引：
下面是輔助索引：
從圖中看得出來，葉子節點中只存儲著地址（也就是此值對應的記錄的所在地址），找到對應的地址，然後去地址中取出數據。並且主鍵索引和輔助索引並沒有太多區別。
然後再來看innodb中的B+樹：
下面是主鍵索引：
下面是輔助索引：
innodb的主鍵索引和實際數據是綁定在一起的也就是說innodb的表一定要有一個主鍵索引，如果一個表沒有手動創建一個主鍵索引，innodb會查看有沒有唯一索引，如果有，則選用唯一索引作為主鍵，如果連唯一索引也沒有，則會默認建立一個隱藏的主鍵索引（用戶不可見）
另外，innodb的主鍵索引要比myisam的的主鍵索引查詢效率較高（少一次磁碟io）,並且比輔助索引也要高很多。（這裡不是很理解。。。。）
所以，我們在使用innodb作為存儲引擎時，要注意：
1.手動建立一個主鍵索引
2.盡量利用主鍵索引進行查詢
默默表示，看到這裡對主鍵索引，輔助索引，聚族索引，非聚族索引有點理解不過來了。。。
後面慢慢緩衝。。
回到我們的問題:為什麼一個節點為1頁(16k) 就夠了?
對著上面Mysql中Innodb中對B+樹的實際應用(主要看主鍵索引)，我們可以發現，B+樹中的一個節點存儲的內容是:
非葉子節點 : 主鍵+指針
葉子節點 : 數據
那麼，假設我們一行數據大小為1K,那麼一頁就能存16條數據，也就是一個葉子節點能存16條數據;
再看非葉子節點，假設主鍵ID為bigint類型, 那麼長度為8B，指針大小在Innodb源碼中為6B，-共就是14B,那麼一頁里就可以存儲16K/14=1170個(主鍵+指針)，那麼一顆高度 為2的B+樹能存儲的數據為:
1170*16=18720條，一 顆高度為3的B+樹能存儲的數據為: 1170*1170*16=21902400 (千萬級條)。所以在InnoDB中B+樹高度一般為1-3層， 它就能滿足千萬級的數據存儲。在查找數據時一次頁的查找代表一次IO,所以通過主鍵索引查詢通常只需要1-3次IO操作即可查找到數據。所以也就回答了我們的問題，1 頁=16k這麼設置是比較合適的，是適用大多數的企業的，當然這個值是可以修改的，所以也能根據業務的時間情況進行調整。
接著，我們來聯繫這次學到的索引底層原理再來看看我常常見到的最左前輟原則：
比如有下面這個B+樹索引，我們建立了一個聯合索引，順序是emp_no,title,from_data.既然是聯合索引，那麼它們按理說應該是放在一起連續存放的。
我們判斷一 個查詢條件能不能用到索引,我們要分析這個查詢條件能不能利用某個索引縮小查詢範圍
對於select * from employees.titles where emp_ no = 1是能用到索引的，因為它能利用上面的索引縮小所有查詢範圍，首先和第一個節點"4-r-01"比較，1<4, 所以可以直接確定結果在左子樹，同理，依次按順序進行比較，逐步可以縮小查詢範圍。
對於select * from employees. titles where title =『1』是不能用到索引的，因為它不能用到上面的索引，和第一節點進行比較時，沒有emp_ no這個欄位的值，不能確定到底該去左子樹還是右子樹繼續進行查詢。
對於select * from employees.titles where title =『1』and emp_ no = 1是能用到索引，按照我們的上面的分析,先用ttle=1 這個條件和第一個節點進行比較，是沒有結果的，但是mysql會對這個sql進行優化，優化之後會將emp_ no=1這個條件放到第一位，從而可以利用索引。這裡是使用了mysql的查詢優化器。
Mysq總結
1. B+樹可以更好的結合磁碟IO原理提高查詢效率
2. Innodb一 定要有主鍵，沒有主鍵會以唯一索引為主鍵， 否則會建立一個隱藏主鍵
3. Innodb的數據是和主鍵索引存在一起的(數據在葉子節點中，MyISAM中的葉子節點存儲的數據地址)
4.建立索引時要考慮已有索引，一個SQL語句只會選擇花費最低的一個索引執行
5.索引是一種有序的數據結構(B+樹) ，一個節點可以存多個有序的元素，所以要利用好最左前綴原則6.真實場景中一顆B+樹的高度通常為3
感覺這裡涉及的知識比較多，需要好好消化，後面再進行深入理解。
歡迎交流討論。
推薦閱讀：
