InnoDB索引方案

為了使用二分法快速定位具體的目錄項，假設所有目錄項都可以在物理存儲器上連續存儲，有以下問題：

• InnoDB使用頁為管理存儲空間的基本單位，最多只能保證16KB的連續存儲空間，記錄數據量多可能需要非常大的連續存儲空間才能放下所有目錄項
• 增刪操作，如果把某頁的記錄都刪除，則該頁及目錄項都沒有存在的必要，如果要把后面的目錄項都向前移，牽一發而動全身；如果不移動作為冗余放在目錄項列表，浪費存儲空間
  復用存儲用戶記錄的數據頁來存儲目錄項，record_type=1標志目錄項記錄
  

目錄項記錄和普通用戶記錄的不同點

• 目錄項記錄record_type為1，普通用戶記錄的record_type為0
• 目錄項記錄只有主鍵值和頁的編號兩個列，普通用戶記錄的列由用戶自己定義，可能包含多列，還有InnoDB自己添加的隱藏列
• 只有目錄項記錄的min_rec_flag屬性為1，普通用戶記錄的min_rec_flag屬性都是0
  

如果存儲目錄項的頁也很多，則為這些存儲目錄項記錄的頁再生成一個更高級的目錄
真正的用戶記錄都存放在B+樹🌲的葉子節點上【第0層】
Page Header部分PAGE_LEVEL屬性代表這個數據頁作為節點在B+樹中的層級

聚簇索引

B+樹本身就是一個目錄/一個索引，有以下兩個特點：

• 使用記錄主鍵值的大小進行記錄和頁的排序
  • 頁【包括葉子節點和內節點】內的記錄按照主鍵的大小排序排成一個單向鏈表，頁內的記錄被劃分成若干個組，每個組中主鍵值最大的記錄在頁內的偏移量會被當作槽依次放在頁目錄項中，可以在頁目錄中通過二分法快速定位到主鍵列等于某值的記錄
  • 各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈表
  • 存放目錄項記錄的頁分為不同的層級，在同一層級中的頁也是根據頁中目錄項記錄的主鍵大小排序排成一個雙向鏈表
• B+樹的葉子節點存儲的是完整的用戶記錄【所有列的值，包括隱藏列】
  在InnoDB存儲引擎中，聚簇索引就是數據的存儲方式【索引即數據，數據即索引】

二級索引

聚簇索引只能在搜索條件是主鍵值時才能發揮作用【B+樹中的數據都是按照主鍵進行排序】
多建幾顆B+樹，不同的B+樹中的數據采用不同的排序規則

與聚簇索引的不同：

• 使用記錄c2列的大小進行記錄和頁的排序
  • 頁【包括葉子節點和內節點】內的記錄是按照c2列的大小順序排成的一個單向鏈表，頁內的記錄被劃分成若干個組，每個組中c2列值最大的記錄在頁內的偏移量會被當作槽一次存放在頁目錄中
  • 各個存放用戶記錄的頁也是根據頁中記錄的c2列大小順序排成的一個雙向鏈表
  • 存放目錄項記錄的頁分為不同的層級，在同一層級中的頁也是根據頁中目錄項記錄的c2列大小順序排成一個雙向鏈表
• B+樹的葉子節點存儲的不是完整的用戶記錄，而只是c2列+主鍵這兩個列的值
• 目錄項記錄中不再是主鍵+頁號的搭配，變成了c2列+頁號的搭配
  C2列并沒有唯一性約束，也就是說滿足搜索條件c2=4的記錄可能有多條，只需要在該B+樹的葉子節點處定位到第一條滿足搜索條件c2=4的記錄，然后沿著由記錄組成的單向鏈表一直向后掃描即可**【頁內的記錄是按照c2列的大小順序排成的一個單向鏈表】，各個葉子節點組成了雙向鏈表**，搜索完了本頁記錄后可以跳到下一頁面中第一條記錄繼續向后掃描
  查找c2=4記錄的過程：

1. 確定第一條符合條件的目錄項記錄所在的頁【定位到頁42（2<4<9）】
2. 通過第一條符合條件的目錄項記錄所在的頁面確定第一條符合條件的用戶記錄所在的頁【定位到第一條符合c2=4的用戶記錄所在頁為34/35（2<4≤ 4）】
3. 在真正存儲第一條符合條件的用戶記錄的頁中定位到具體的記錄【如果在頁34定位到第一條就不需要再到頁35定位第一條記錄】
4. 這個B+樹只記錄了c2和主鍵兩個列，在定位到第一條符合條件的用戶記錄后，需要根據該記錄中的主鍵信息到聚簇索引中查找到完整的用戶記錄，這個通過攜帶主鍵信息到聚簇索引中重新定位完整記錄的過程也稱為回表，然后再返回到這顆B+樹葉子節點處沿單向鏈表繼續向后搜索其他滿足條件的記錄【找到一條就去聚簇索引找到完整記錄】
   因為需要回表才能獲取完整的記錄，這種B+樹也稱為二級索引/輔助索引

聯合索引/復合索引/多列索引

可以同時以多個列的大小作為排序規則，即同時為多個列建立索引

• 每條目錄項記錄都由c2列、c3列、頁號這三部分組成，記錄先按c2列的值進行排序，c2相同的情況下再按照c3列的值進行排序
• B+樹葉子節點處的用戶記錄由c2列、c3列和主鍵c1組成
  本質上也是一個二級索引

InnoDB中B+樹索引的注意事項

1. 根頁面萬年不動窩【頁號不再改變】【存簇索引根節點在某個頁面，數據字典中的一項信息】
   1. 每當為某個表創建B+樹索引【聚簇索引默認存在】時，就會為這個索引創建一個根節點頁面，最開始表中沒有數據的時候，每個B+樹索引對應的根節點中既沒有用戶記錄也沒有目錄項記錄
   2. 向表中插入用戶記錄時，先把用戶記錄存儲到這個根節點中
   3. 在根節點中可用空間用完時繼續插入記錄，1??將根節點中所有記錄復制到一個新分配的頁a中，2??對這個新頁進行頁分裂操作，3??得到另一個新頁b，新插入的記錄會根據鍵值【主鍵值/二級索引對應的索引列值】的大小分配到頁a/頁b中，根節點升級為存儲目錄項記錄的頁，需要把頁a和頁b對應的目錄項記錄插入到根節點中【由空葉子節點形成樹的過程】
2. 內節點中目錄項記錄的唯一性

   1. 目錄項記錄的內容是索引列加頁號的搭配，但對于二級索引來說不夠嚴謹，為了讓新插入的記錄找到在哪個頁，需要保證B+樹同一層內節點的目錄項記錄除頁號字段以外是唯一的【二級索引內節點的目錄項記錄的內容由：索引列的值、主鍵值、頁號構成】

   2. 

   3. 圖6-16如果插入列值為1的記錄，則該記錄會找不到該往頁4插還是頁5

   4. 如圖6-17，先把新記錄的列值與頁3各目錄項記錄的列值比較，如果列值相同，可以接著比較主鍵，B+樹同一層中不同目錄項記錄的列值+主鍵的值肯定不同，最后肯定能定位到唯一一條目錄項記錄

   5. 對二級索引記錄來說，先按二級索引列的值進行排序，如果列值相同的情況下，再按主鍵值排序，為c2列建立索引相當于為(c2,c1)列建立一個聯合索引

   6. 對于唯一二級索引【當為某列或列組合聲明UNIQUE屬性時，便會為這個列或列組合建立唯一二級索引】來說，也可能會出現多條記錄鍵值相同的情況【聲明為UNIQUE屬性的列可能存儲多個NULL值；MVCC服務】，唯一二級索引的內節點的目錄項記錄也會包含記錄的主鍵值

3. 一個頁面至少容納2條記錄
   1. InnoDB一個數據頁至少可以存放2條記錄，如果只能存放一條則目錄層級會非常多，最后葉子節點也只有一條記錄，效率大打折扣
   2. 如果B+樹葉子節點只存儲一條記錄，內節點存儲多條記錄也是可以發揮B+樹作用的，但是為了避免B+樹層級增長過高，InnoDB要求所有數據頁都至少可以容納兩條記錄