聚簇索引

有兩個特點

1. 使用主鍵值大小進行紀錄和頁的排序
   包含三個方面

   • 頁內的所有紀錄(包含使用者紀錄與目錄項紀錄)按照主鍵值大小形成一個單向鏈結串列，紀錄被劃分成多組，且每組主鍵最大的紀錄偏移量會被取出當作槽依序放在頁目錄中，讓我們可以在頁目錄中快速透過二分法定位到我們要找的指定紀錄。
   • 存放使用者紀錄的頁也是根據紀錄主鍵值大小順序排成一個雙向鏈結串列
   • 存放目錄項紀錄的頁在同一個階層也是根據紀錄主鍵值大小順序排成一個雙向鏈結串列

2. B+樹的葉子節點儲存的是完整的使用者紀錄。所謂的完整使用者紀錄就是指這個紀錄儲存了所有列的值(包含隱藏列)
   這邊額外補充說明一下什麼是隱藏列(跟前文無關，知道的人可以略過)。就要提到Innodb的主鍵生成策略，它會優先使用使用者自訂的主鍵作為主鍵，如果使用者沒有定義主鍵，則選取一個不允許NULL的UNIQUE值作主鍵，如果連不允許NULL的UNIQUE值都沒有定義，則Innodb會為表預設增加一個名為row_id的隱藏列作為主鍵。

我們把具有這兩個特點的B+樹稱為聚簇索引，所有完整的使用者紀錄都存放在這個聚簇索引的葉子節點。聚簇索引不需要我們在Mysql敘述中顯性的使用INDEX敘述去創建（這邊不懂沒關係，後面會在介紹），Innodb儲存引擎會自動替我們創建聚簇索引。

二級索引

大家是否發現，聚簇索引只能在搜尋條件是主鍵值時發揮作用，原因是B+樹中的資料都是按照主鍵排序的。那如果我們想以別的列作為搜尋條件該怎麼辦呢？難道只能從頭到尾沿著鏈結串列依次歷遍紀錄嗎？
當然不是！做法是我們可以多建幾棵B+樹，不同的B+樹採用不同的排序規則。

舉個例子：
我們可以只用c2列數值做資料頁
那這個B+樹跟前面聚簇索引的B+樹有那些不同呢？

1. 變成使用c2列的大小進行紀錄和頁的排序
   包含三個方面

   • 頁內的所有紀錄(包含使用者紀錄與目錄項紀錄)按照c2列的大小形成一個單向鏈結串列，紀錄被劃分成多組，且每組c2列最大的紀錄其偏移量會被取出當作槽依序放在頁目錄中，讓我們可以在頁目錄中快速透過二分法定位到我們要找的c2列等於某個值的紀錄。
   • 存放使用者紀錄的頁也是根據紀錄c2列大小順序排成一個雙向鏈結串列
   • 存放目錄項紀錄的頁在同一個階層也是根據紀錄c2列大小順序排成一個雙向鏈結串列

2. B+樹的葉子節點儲存的並不是完整的使用者紀錄。只有c2列+c1列(主鍵)這兩個列的值

3. 目錄項紀錄不再是主鍵+頁號的搭配，而是c2列+頁號

這邊搜尋的流程也會有些許的不同：

假設我們要找尋紀錄c2=4
我們由上而下透過c2=4，使用二分法先定位到目錄項，再定位到使用者紀錄。
發現使用者紀錄內只有c2列跟主鍵的值，並不是完整的使用者紀錄。
所以我們必須再拿主鍵值回到聚簇索引內去查詢完整的使用者紀錄，這個過程又叫做回表。

此外由於c2列的值並沒有唯一性(主鍵才有唯一性)，可能會有很多筆紀錄符合c2=4，所以我們會從找到的第一筆紀錄(c2=4)開始沿著單向鏈結串列往下找，每找到一筆就進行回表操作。重複這個過程直到不滿足c2=4條件停止。

就是因為這種以非主鍵列的大小排序建立的B+樹需要執行回表操作才可以定位到完整的使用者紀錄，所以這種B+樹才稱為二級索引(輔助索引)。

聯合索引

我們也可以用多列作排序，就是為多個列建立索引。
比如我們想讓B+樹按照c2和c3列的大小進行排序，這裡面包含兩層含義：

1. 先把各紀錄和頁照c2列排序
2. 在c2列相同的情況下，再採用c3列排序

這棵樹每筆目錄項紀錄就會是由c2列、c3列、頁號3個部分組成。
(補充說明一下：前面二級索引是c2列+頁號，一樣畫葫蘆，就是c2列、c3列、頁號)
而使用者紀錄(葉子節點)是由c2列、c3列、c1列(主鍵)3個部分組成。
這樣的B+樹就稱為聯合索引，也稱複合索引或多列索引。本質上也是個二級索引。

要特別注意的是
以c2和c3列為排序建立聯合索引和分別為c2和c3列建立索引是不同的概念唷！
不同點為
建立聯合索引是建立一棵B+樹(先按照c2排序，c2相同再用c3排序)
而分別為c2和c3列建立索引，則會分別以c2和c3列為排序建立兩棵B+樹

Innodb中B+樹索引的相關注意事項

1. 根頁面是萬年不動的
   當我們為某表創建B+樹索引時，都會為索引創建一個根節點頁。最開始根節點沒有任何資料。
   之後開始插入使用者紀錄會先把其儲存到根節點，當根節點的可用空間用完時，如還要繼續插入新紀錄，這時會把先根節點內的所有紀錄複製到新頁A，然後對這個頁面進行頁分裂(如果不清楚可以回前一篇複習)操作，得到另一個新頁B。然後再往下繼續插入，新紀錄會根據鍵值(聚簇索引中的主鍵值，或二級索引中對應索引列的值)大小插入到頁A或頁B中。此時根節點便升級為儲存目錄項紀錄的頁(還記得第一層是使用者紀錄層，第二層含以上都是目錄項紀錄層唷)，此時也需把頁A和頁B對應的目錄項紀錄插入到根節點中。
   這邊要注意的是B+樹索引根節點自創建日便再也不移動(頁號再也不改變)。

2. 內節點中目錄項紀錄的唯一性
   我們知道搜尋非主鍵值以外的列時，我們會建立二級索引，而二級索引的目錄項紀錄是索引列(c2)加頁號，但這樣會有問題。
   舉個例子：
   有一目錄項頁面，內有2筆目錄項紀錄( [c2:1,頁號:1] 跟 [c2:1,頁號:2] )，c2的值都為1，分別對應到第1頁與第2頁。
   這時欲插入一筆新紀錄[c2:1]
   原先我們透過二分法，用c2=1去查詢屬於那一目錄項，進而知道要插入到那頁(第1頁或第2頁)
   但現在發現c2的值與原先的2筆紀錄一樣@@，我們就不知道要插入到那一頁了...
   因此為了讓新插入的紀錄能找到自己屬於那一頁，我們就需要保證B+樹同一層內節點的目錄項紀錄，除了頁號這個欄位以外是唯一的。
   二級索引內節點的目錄項紀錄從原先的索引列(c2)加頁號，追加主鍵值變成索引列(c2)加c1(主鍵值)加頁號
   這樣即可確保搜尋到唯一一筆目錄項紀錄。

耶！take a break
接下來我們會具體說明該如何使用B+樹索引，敬請期待