摘要 本文介紹MySQL的InnoDB索引相對底層原理相關知識，涉及到B+Tree索引和Hash索引，但本文主要介紹B+Tree索引，其中包括聚簇索引和非聚簇索引，InnoDB資料頁結構詳解，B+Tree索引的使用以及優化，同時還有B+Tree索引的查詢流程簡介。 此文是我對學習InnoDB索引的一個總結，内容主要參考MySQL技術内幕 InnoDB存儲引擎一書，及網上一些部落格（參考文獻會給出） 一、先從B+Tree入手 B+樹的特性 因作者文筆有限，B+樹的定義如果在這裡重複列出的話，應該隻會讓大家更困惑，同時相信任何一本資料結構書中都能找到其複雜的定義。但是為了便于讀者了解接下來的内容，下面隻是簡單的介紹一下B+樹的幾個本文中會用到的特性。 B+樹是為磁盤或其他直接存取輔助裝置而設計的一種平衡查找樹（如果不知道平衡查找樹，請自行google），在B+樹中，所有記錄節點都是按鍵值的大小順序存放在同一層的葉節點中，各葉節點指針進行連接配接。 下圖是在網上找的一張B+樹示意圖
二、InnoDB資料頁結構 1.頁介紹 頁是InnoDB存儲引擎管理資料庫的最小磁盤機關。 頁類型為B-Tree node的頁，存放的即是表中行的實際資料了。 InnoDB中的頁大小為16KB，且不可以更改 InnoDB可以将一條記錄中的某些資料存儲在真正的資料頁面之外，即作為行溢出資料。MySQL的varchar資料類型可以存放65535個位元組，但 實際隻能存儲65532個 。同時InnoDB是B+樹結構的，是以 每個頁中至少應該有兩個行記錄 ，否則失去了B+樹的意義，變成了連結清單，是以一行記錄 最大長度的門檻值是8098 ，如果大于這個值就會将其存到溢出行中。
2.InnoDB資料頁組成部分 File Header(檔案頭) Page Header(頁頭) Infimun + Supremum Records User Records(使用者記錄，即行記錄) Free Space(空閑空間) Page Directory(頁目錄) File Trailer(檔案結尾資訊) 這也是我摘抄的書上的内容，下面我隻介紹一下會幫助了解底層原理的部分。
1.在File header中，FIL+PAGE_PREV,FIL_PAGE_NEXT兩個表示目前頁的上一頁和下一頁，由此可以看出 葉子節點是雙向連結清單串起來的 。如下圖
2.Infimum和Supremum記錄 在InnoDB存儲引擎中，每個資料頁中有兩個虛拟的行記錄，用來限定記錄的邊界。Infimum記錄是比該頁中任何主鍵值都要小的值，Supremum指比任何可能大的值還要大的值。這兩個值在頁建立時被建立，并且在任何情況下不會被删除。
由上圖可以看出，行記錄是記錄在頁中的，同時是在頁内行記錄之間也是雙向連結清單連結的(在網上有看到說是單連結清單的) 3.Page Directory 頁目錄中存放了記錄的相對位置，有些時候這些記錄指針稱為Slots（槽）或者目錄槽，與其他資料庫不同的是， InnoDB并不是每個記錄擁有一個槽 ，InnoDB中的槽是一個稀疏目錄，即一個槽中可能屬于多個記錄，最少屬于4個目錄，最多屬于8個目錄。槽中記錄按照鍵順序存放，這樣可以利用二叉查找迅速找到記錄的指針。 但是由于InnoDB中的Slots是稀疏目錄，二叉查找的結果隻是一個粗略的結果 ，是以InnoDB必須通過recorder header中的next_record來繼續查找相關記錄。同時slots很好的解釋了recorder header中的n_owned值的含義，即還有多少記錄需要查找，因為這些記錄并不包括在slots中。
三、查詢B+樹索引的流程 首先通過B+樹索引找到葉節點，再找到對應的資料頁，然後将資料頁加載到記憶體中，通過二分查找Page Directory中的槽，查找出一個粗略的目錄，然後根據槽的指針指向連結清單中的行記錄，之後在連結清單中依次查找。 需要注意的地方是， B+樹索引不能找到具體的一條記錄 ，而是隻能找到對應的頁。 把頁從磁盤裝入到記憶體中 ，再通過 Page Directory進行二分查找 ，同時此 二分查找也可能找不到具體的行記錄 （有可能會找到），隻是能找到一個接近的連結清單中的點，再從此點開始周遊連結清單進行查找。
四、聚簇索引與非聚簇索引 B+樹索引可以分為聚集索引和輔助索引，他們不同點是，聚集索引的行資料和主鍵B+樹存儲在一起，輔助索引隻存儲輔助鍵和主鍵。 1.聚集索引 聚集索引是按每張表的主鍵構造的一顆B+樹，并且葉節點中存放着整張表的行記錄資料，是以也讓聚集索引的節點成為資料頁，這個特性決定了索引組織表中資料也是索引的一部分。由于實際的資料頁隻能按照一顆B+樹進行排序，是以每張表隻能擁有一個聚集索引。查詢優化器非常傾向于采用聚集索引，因為其直接存儲行資料，是以主鍵的排序查詢和範圍查找速度非常快。 不是實體上的連續，而是邏輯上的，不過在剛開始時資料是順序插入的是以是實體上的連續，随着資料增删，實體上不再連續。 2.輔助索引 輔助索引頁級别不包含行的全部資料。葉節點除了包含鍵值以外，每個葉級别中的索引行中還包含了一個書簽，該書簽用來告訴InnoDB哪裡可以找到與索引相對應的行資料。其中存的就是聚集索引的鍵。 輔助索引的存在并不影響資料在聚集索引的結構組織。InnoDB會周遊輔助索引并通過葉級别的指針獲得指向主鍵索引的主鍵，然後通過主鍵索引找到一個完整的行記錄。當然如果隻是需要輔助索引的值和主鍵索引的值，那麼隻需要查找輔助索引就可以查詢出索要的資料，就不用再去查主鍵索引了。
五、索引的管理 索引在建立或者删除時，MySQL會先建立一個新的臨時表，然後把資料導入臨時表，删除原表，再把臨時表更名為原表名稱。 但是在InnoDB Plugin版本開始，支援快速建立索引。其原理是先在InnoDB上加一個s鎖，在建立過程中不需要建表，是以速度會很快。建立過程中由于加了s鎖，是以隻能進行讀操作，不能寫操作。 show index form table;是檢視表中索引的資訊的。 Table:索引所在的表名 Non_unique:非唯一的索引，可以看到primary key 是0，因為必須是唯一的 Key_name:索引名稱 Seq_in_index:索引中該列的位置 Column_name:索引的列 Collation:列以什麼方式存儲在索引中。可以是A或者NULL，B+樹索引總是A，即排序的。 Cardinality：表示索引中唯一值的數目的估計值。如果非常小，那麼需要考慮是否還需要建立這個索引了。優化器也會根據這個值來判斷是否使用這個索引。 Sub_part:是否是列的部分被索引。100表示隻索引列的前100個字元。 Packed:關鍵字如果被壓縮。 Null：是否索引的列含有NULL值。 Index_type:索引的類型。InnoDB隻支援B+樹索引，是以顯示BTREE
六、Hash索引 InnoDB中自适應哈希索引使用的是散清單的資料結構，并且DBA無法幹預。 其實這一部分的原理，非常簡單，在此就不做過多介紹了
總結 至此本文就結束了，本文隻是從原理上進行了簡單的介紹，由于筆者水準有限，且了解不深入，本文多處借鑒書本知識。外加了一些自己的見解，如有錯誤之處，還請不吝賜教。其中參考的部落格位址： http://www.admin10000.com/document/5372.html ，同時還有eremy Cole的部落格，位址： https://blog.jcole.us/2013/01/14/efficiently-traversing-innodb-btrees-with-the-page-directory/