一. 索引

　　在上一章節中健哥講解了索引的基本入門和使用進階。那么在這一節中我們來探討下索引的深層原理。各位小伙伴準備好了嗎，我們開始嘍!

　　索引的實現原理

　　索引是在MySQL的存儲引擎中實現的，所以每種存儲引擎的索引也就各不相同了，不同的存儲引擎支持不同類型的索引。這里我們主要研究InnoDB引擎實現的B+樹索引。

　　B+樹是一種數據結構。通常使用在數據庫和操作系統中的文件系統，特點是能夠保持數據穩定有序，還能夠加快查詢速度，我們一起來看下吧。

　　磁盤存儲

　　系統從磁盤讀取數據到內存時是以磁盤塊(block)為基本單位的。

　　位于同一個磁盤塊中的數據會被一次性讀取出來，而不是需要什么取什么。

　　InnoDB存儲引擎中有頁(Page)的概念，頁是其磁盤管理的最小單位。InnoDB存儲引擎中默認每個頁的大小為16KB。

　　InnoDB引擎將若干個地址連接磁盤塊，以此來達到頁的大小16KB，在查詢數據時如果一個頁中的每條數據都能有助于定位數據記錄的位置，這將會減少磁盤I/O次數，提高查詢效率。

　　BTree

　　BTree結構的數據可以讓系統高效的找到數據所在的磁盤塊。為了描述BTree，首先定義一條記錄為一個二元組[key, data] ，key為記錄的鍵值，對應表中的主鍵值，data為一行記錄中除主鍵外的數據。對于不同的記錄，key值互不相同。BTree中的每個節點根據實際情況可以包含大量的關鍵字信息和分支，如下圖所示為一個3階的BTree：

　　根據圖中結構顯示，每個節點占用一個盤塊的磁盤空間，一個節點上有兩個升序排序的關鍵字和三個指向子樹根節點的指針，指針存儲的是子節點所在磁盤塊的地址。兩個關鍵詞劃分成的三個范圍域對應三個指針指向的子樹的數據的范圍域。以根節點為例，關鍵字為17和35，P1指針指向的子樹的數據范圍為小于17，P2指針指向的子樹的數據范圍為17~35，P3指針指向的子樹的數據范圍為大于35。

　　查找順序,模擬查找15的過程 ：

　　● 根節點找到磁盤塊1，讀入內存。【磁盤I/O操作第1次】比較關鍵字15在區間(<17)，找到磁盤塊1的指針P1。

　　● P1指針找到磁盤塊2，讀入內存。【磁盤I/O操作第2次】比較關鍵字15在區間(>12)，找到磁盤塊2的指針P3。

　　● P3指針找到磁盤塊7，讀入內存。【磁盤I/O操作第3次】 在磁盤塊7中找到關鍵字15。

　　● 分析:

　　○ 發現需要3次磁盤I/O操作，和3次內存查找操作。

　　○ 由于內存中的關鍵字是一個有序表結構，可以利用二分法查找提高效率。而3次磁盤I/O操作是影響整個BTree查找效率的決定因素。BTree使用較少的節點個數，使每次磁盤I/O取到內存的數據都發揮了作用，從而提高了查詢效率。

　　4. B+Tree

　　B+Tree是在BTree基礎上的一種優化，使其更適合實現外存儲索引結構，InnoDB存儲引擎就是用B+Tree實現其索引結構。

　　從上一節中的BTree結構圖中可以看到每個節點中不僅包含數據的key值，還有data值。而每一個頁的存儲空間是有限的，如果data數據較大時將會導致每個節點(即一個頁)能存儲的key的數量很小，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁盤I/O次數，進而影響查詢效率。在B+Tree中，所有數據記錄節點都是按照鍵值大小順序存放在同一層的葉子節點上，而非葉子節點上只存儲key值信息，這樣可以大大加大每個節點存儲的key值數量，降低B+Tree的高度。

　　B+Tree相對于BTree區別：

　　● 非葉子節點只存儲鍵值信息。

　　● 所有葉子節點之間都有一個連接指針。

　　● 數據記錄都存放在葉子節點中。

　　通常在B+Tree上有兩個頭指針，一個指向根節點，另一個指向關鍵字最小的葉子節點，而且所有葉子節點(即數據節點)之間是一種鏈式環結構。

　　對B+Tree進行兩種查找運算：

　　● 【有范圍】對于主鍵的范圍查找和分頁查找。

　　● 【有順序】從根節點開始，進行隨機查找。

　　實際情況中每個節點可能不能填充滿，因此在數據庫中，B+Tree的高度一般都在24層。MySQL的InnoDB存儲引擎在設計時是將根節點常駐內存的，也就是說查找某一鍵值的行記錄時最多只需要13次磁盤I/O操作。