在設計資料表的過程中索引的設計會跟查詢效率有直接的關係，隨著數據量的增加一條查詢SQL語句有無吃到index對執行上的效率差異是明顯可見的。

套用索引最常看到的比喻，index(索引)就像是書的目錄。

有了目錄你就能根據上面定位好的頁數紀錄去找到對應資料，相反的沒有這些目錄，你就得慢慢的去找到你要的內容(全表掃描)。

MySQL數據路徑底下的資料庫檔案內可以看到，InnoDB儲存資料庫資料有3個檔案分別為:

• db.opt
  .opt檔紀錄該資料庫預設字符集編碼和字符集排序規則。

• table_name.frm
  .frm檔存放這個表的相關資料(表結構定義)資訊。

• table_name.ibd
  .ibd檔存放這個表的資料與索引內容。
  InnoDB表資料檔案本身就是按B+Tree組織的主索引結構，資料與索引的儲存以Clustered Index來聚集組織。

InnoDB將索引分成Cluster Index & Secondary Index

• 聚集索引 Clustered Index (primary Index) 是什麼？

  • 先看MySQL如何選擇Clustered key規則:

    1. 建表時有primary key，選primary key。

    2. 沒有primary key的話，選第一個not null的unique key。

    3. 以上都沒有，產生一個auto increment的隱藏欄位做clustered key。

    4. 每個表只會有一個Clustered Index(表紀錄只能用一種物理順序存放)

  • InnoDB採用B+Tree來作為組織實現儲存資料的主索引結構，用以下圖來解釋～

    • leaf node(葉節點) 真正存資料的地方
      儲存主鍵值的row data和一個指向相鄰節點的指標。

    • 非葉節點
      儲存key的值和指向child node的指標，作用在定位到具體的紀錄位置。

    • 左閉合區間查詢
      查詢資料採用左閉合區間查詢。 ex.[a,b) =包含a但不包含b的區間範圍。

運作邏輯:

還記得在前面InnoDB架構介紹時有提到資料與索引都是儲存在磁碟中的，要使用的話會先將資料所在的page載入內存中才進行動作。內存和磁盤以page為單位交換資料!!
那問題來了當數據量大的時候，索引檔案的大小可能會很大，總不能直接用一次性的載入memory，所以在資料查詢時會分多次磁碟IO逐一加載disk page(對應B+tree的node)，將索引相關資料分批載入memory。從根節點開始逐層索引到葉節點後返回資料。

• Page
  InnoDB磁盤管理的最小儲存單位。page default: 16KB <-最多存放16KB的資料

• 針對B+Tree架構整理以下特點:

  • Clustered Index: 決定了資料的分布。換句話來說當表的建立起來後，資料表中的資料排序方式會依照clustered index 的key值來排序。

引用官方敘述
If index records are inserted in a sequential order (ascending or descending), the resulting index pages are about 15/16 full. If records are inserted in a random order, the pages are from 1/2 to 15/16 full.
可見存放資料時不會把全page空間都用完，而是保留一部分做日後的新增更新。紀錄循序插入page維持在約15/16滿，紀錄亂序插入的話page維持在約1/2~15/16滿。

• 主鍵值的有序與無序影響塞資料的效能和page空間使用率

上面提到資料會按照主鍵值順序存放，對於有序主鍵值(ex.自增ID)來說，當我們新增一筆資料時，mysql根據主鍵值將其插入當前索引節點的後續位置，不需做額外的搬動，當page到達(15/16)後，開一個新page存放資料。那當使用(值不重複的隨機值PK)就會遇到需要插入到現有page的某個位置，造成page之間的資料搬動，增加效能上的開銷。

以上圖B+tree結構舉例來說，當我要查找ID=26的這筆資料

第一次IO:

• 將根節點page載入內存判斷主索引值位於哪個子節點page。
  • 範圍: (21<= 26 <45) -> 走中間線到子節點的第二個page

第二次IO:

• 取出子節點的第二個page，載入內存中判斷。
  • 範圍: (25<= 26 <30) -> 走中間線到達存放資料所在的葉節點page

第三次IO:

• 取出葉節點資料所在page，載入內存中。
  • 命中 ID= 26 這筆紀錄返回。

看完以上內容對於InnoDB主索引架構有了基本的認識，有一個部分在這篇我沒提到，有興趣可以去看看～就是MySQL為何選擇了B+Tree? B+tree & B-tree差異在哪？

像是針對只有葉節點才存放資料的特性可以比對出以下差異～

• (B+tree)在子節點上因為沒有存放資料，所以在一個page 16K限制下相比(B-tree)能存放更多的key，B+tree磁碟讀寫更好，一次的IO載入資料量更多。

• (B+tree) key相關的資料只存在葉節點上，保證查詢的穩定，都要到達葉節點後才拿得到資料。而(B-tree)在子節點中存放資料，命中key就能拿到資料。

明天來介紹Secondary Index～