各個數據頁可以組成一個`雙向鏈表`，而每個數據頁中的記錄會按照主鍵值從小到大的順序組成一個`單向鏈表`，每個數據頁都會為存儲在它里邊兒的記錄生成一個`頁目錄`，在通過主鍵查找某條記錄的時候可以在`頁目錄`中使用二分法快速定位到對應的槽，然后再遍歷該槽對應分組中的記錄即可快速找到指定的記錄  `目錄項記錄`和普通的`用戶記錄`的不同點： * `目錄項記錄`的`record_type`值是1，而普通用戶記錄的`record_type`值是0。 * `目錄項記錄`只有主鍵值和頁的編號兩個列，而普通的用戶記錄的列是用戶自己定義的，可能包含很多列，另外還有`InnoDB`自己添加的隱藏列。 * `min_rec_mask`，只有在存儲`目錄項記錄`的頁中的主鍵值最小的`目錄項記錄`的`min_rec_mask`值為`1`，其他別的記錄的`min_rec_mask`值都是`0`。 #### 聚簇索引 1. 使用記錄主鍵值的大小進行記錄和頁的排序，這包括三個方面的含義： * 頁內的記錄是按照主鍵的大小順序排成一個單向鏈表。 * 各個存放用戶記錄的頁也是根據頁中用戶記錄的主鍵大小順序排成一個雙向鏈表。 * 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的主鍵大小順序排成一個雙向鏈表。 2. `B+`樹的葉子節點存儲的是完整的用戶記錄。 所謂完整的用戶記錄，就是指這個記錄中存儲了所有列的值（包括隱藏列）。 我們把具有這兩種特性的`B+`樹稱為`聚簇索引`，所有完整的用戶記錄都存放在這個`聚簇索引`的葉子節點處。這種`聚簇索引`并不需要我們在`MySQL`語句中顯式的使用`INDEX`語句去創建（后邊會介紹索引相關的語句），`InnoDB`存儲引擎會自動的為我們創建聚簇索引。另外有趣的一點是，在`InnoDB`存儲引擎中，`聚簇索引`就是數據的存儲方式（所有的用戶記錄都存儲在了`葉子節點`），也就是所謂的索引即數據，數據即索引。 **將數據和索引放到一起存儲**，索引結構的葉子節點保留了數據行。每個表一定會有一個聚集索引，整個表的數據存儲以b+樹的方式存在文件中，**b+樹葉子節點中的key為主鍵值，data為完整記錄的信息；非葉子節點存儲主鍵的值。** #### 二級索引(非聚簇索引) 和聚簇索引區別 * 使用記錄`c2`列的大小進行記錄和頁的排序，這包括三個方面的含義： * 頁內的記錄是按照`索引`列的大小順序排成一個單向鏈表。 * 各個存放用戶記錄的頁也是根據頁中記錄的`索引`列大小順序排成一個雙向鏈表。 * 存放目錄項記錄的頁分為不同的層次，在同一層次中的頁也是根據頁中目錄項記錄的`索引`列大小順序排成一個雙向鏈表。 * `B+`樹的葉子節點存儲的并不是完整的用戶記錄，而只是`索引列+主鍵`這兩個列的值。 * 目錄項記錄中不再是`主鍵+頁號`的搭配，而變成了`索引列+頁號`的搭配。 如果返回的列不在非聚簇索引樹種, 則還需要根據得到的主鍵去聚簇索引里查詢詳細信息, 此過程叫**回表** **覆蓋索引**：索引字段覆蓋了查詢語句涉及的字段，直接通過索引文件就可以返回查詢所需的數據，不必通過回表操作。 ## 索引 * 每個索引都對應一棵`B+`樹，`B+`樹分為好多層，最下邊一層是葉子節點，其余的是內節點。所有`用戶記錄`都存儲在`B+`樹的葉子節點，所有`目錄項記錄`都存儲在內節點。 * `InnoDB`存儲引擎會自動為主鍵（如果沒有它會自動幫我們添加）建立`聚簇索引`，聚簇索引的葉子節點包含完整的用戶記錄。 * 我們可以為自己感興趣的列建立`二級索引`，`二級索引`的葉子節點包含的用戶記錄由`索引列 + 主鍵`組成，所以如果想通過`二級索引`來查找完整的用戶記錄的話，需要通過`回表`操作，也就是在通過`二級索引`找到主鍵值之后再到`聚簇索引`中查找完整的用戶記錄。 * `B+`樹中每層節點都是按照索引列值從小到大的順序排序而組成了雙向鏈表，而且每個頁內的記錄（不論是用戶記錄還是目錄項記錄）都是按照索引列的值從小到大的順序而形成了一個單鏈表。如果是`聯合索引`的話，則頁面和記錄先按照`聯合索引`前邊的列排序，如果該列值相同，再按照`聯合索引`后邊的列排序。 * 通過索引查找記錄是從`B+`樹的根節點開始，一層一層向下搜索。由于每個頁面都按照索引列的值建立了`Page Directory`（頁目錄），所以在這些頁面中的查找非常快。 ## 索引的代價 * 空間 每建立一個索引都要為它建立一棵`B+`樹，每一棵`B+`樹的每一個節點都是一個數據頁，一個頁默認會占用`16KB`的存儲空間，一棵很大的`B+`樹由許多數據頁組成 * 時間 每次對表中的數據進行增、刪、改操作時，都需要去修改各個`B+`樹索引。而增、刪、改操作可能會對節點和記錄的排序造成破壞，所以存儲引擎需要額外的時間進行一些記錄移位，頁面分裂、頁面回收啥的操作來維護好節點和記錄的排序。 `WHERE`子句中的幾個搜索條件的順序對查詢結果沒有影響, MySQL的優化器是很智能的. 1. `B+`樹索引在空間和時間上都有代價，所以沒事兒別瞎建索引。 2. `B+`樹索引適用于下邊這些情況： * 全值匹配 * 匹配左邊的列 * 匹配范圍值 * 精確匹配某一列并范圍匹配另外一列 * 用于排序 * 用于分組 3. 在使用索引時需要注意下邊這些事項： * 只為用于搜索、排序或分組的列創建索引 * 為列的基數大的列創建索引 * 索引列的類型盡量小 * 可以只對字符串值的前綴建立索引 * 只有索引列在比較表達式中單獨出現才可以適用索引 * 為了盡可能少的讓`聚簇索引`發生頁面分裂和記錄移位的情況，建議讓主鍵擁有`AUTO_INCREMENT`屬性。 * 定位并刪除表中的重復和冗余索引 * 盡量使用`覆蓋索引`進行查詢，避免`回表`帶來的性能損耗。