MySQL中的索引模型

Mysql中的索引使用的數據結構一般為搜索樹，這里的搜索樹，一般使用B樹，這里補一下數據結構中的B樹結構；說B樹之前，先順一個前置的知識點，平衡二叉樹；

平衡二叉樹

二叉樹應該都不陌生，大學數據結構的基本入門，二叉排序樹是基于二叉樹上多了個“有序”的概念，簡單來說，即 左 < 右或 右<左，反正就是，樹是按著順序建立的 。

相比較普通的二叉樹，二叉排序樹具有“順序”的特點，但是當極端情況下，即單邊順序排列下去，二叉排序樹就成了單鏈表了，失去了樹的意義，于是在二叉排序樹的基礎上進一步加強，即：滿足二叉排序樹特點同時又左右子樹高度差小于等于1，就有了平衡二叉樹。平衡二叉樹的特點如下： 

1. 二叉排序樹

2. 任何一個節點的左子樹或者右子樹都是「平衡二叉樹」（左右高度差小于等于 1）

B樹

平衡二叉樹已經很好了，其因為順序、且限制了樹的飽和，于是使得平衡二叉樹在檢索時，具有很高的性能，復雜度才O(logN)，此時影響查詢性能的瓶頸就演變到節點數量N了；根據樹的特點，進行比對計算的次數取決于樹的高度，如果節點的數量固定，我們可以通過控制每層的節點數來控制樹的高度，不拘泥于“二叉”這一特性，變成多叉的平衡樹（B-樹）。

B樹是一個絕對平衡樹，所有的葉子節點在同一高度。在每個節點存儲多個元素，在每個節點除了指針節點外，還存儲相應的數據；相比二叉平衡查找樹，在整個查找過程中，雖然數據的比較次數并沒有明顯減少，但是磁盤IO次數會大大減少；B樹的高度一般2至3層就能滿足大部分的應用場景，所以使用B樹構建索引可以很好的提升查詢的效率。

B樹特點

• 每個節點至多可以擁有m棵子樹（m階）。
• 根節點，至少有2個節點。
• 非根非葉的節點至少有的Ceil(m/2)個子樹(Ceil表示向上取整，圖中5階B樹，每個節點至少有3個子樹，也就是至少有3個叉)。
• 非葉節點中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示該節點中保存的關鍵字個數，K為關鍵字且Ki<Ki+1，A為指向子樹根節點的指針。
• 從根到葉子的每一條路徑都有相同的長度，也就是說，葉子節在相同的層，并且這些節點不帶信息，實際上這些節點就表示找不到指定的值，也就是指向這些節點的指針為空。

B+樹

盡管B樹能較為明顯的提升效率，但是它節點攜帶數據這一特征，隨著存儲數據的增長，必然導致空間的占用，如果使用到數據庫索引時，意味著會樹相應就會變高，一個頁中可存儲的數據量就會變少，磁盤IO次數就會變大。

所以引入了B樹的另一增強B+樹，相比于B樹，B+樹的特點在于：

1. 內部節點只存儲鍵值，不存儲數據。數據只存儲在葉子節點中，并且葉子節點包含了全部的鍵值和指向數據的指針。

2. 葉子節點之間有雙向鏈表鏈接，這使得范圍查詢更加高效，因為可以通過鏈表順序訪問葉子節點。

B+樹的最底層葉子節點包含了所有的索引項。從圖上可以看到，B+樹在查找數據的時候，由于數據都存放在最底層的葉子節點上，所以每次查找都需要檢索到葉子節點才能查詢到數據。所以在需要查詢數據的情況下每次的磁盤的IO跟樹高有直接的關系，但是從另一方面來說，由于數據都被放到了葉子節點，所以放索引的磁盤塊鎖存放的索引數量是會跟這增加的，所以相對于B樹來說，B+樹的樹高理論上情況下是比B樹要矮的。也存在索引覆蓋查詢的情況，在索引中數據滿足了當前查詢語句所需要的全部數據，此時只需要找到索引即可立刻返回，不需要檢索到最底層的葉子節點。

索引分類

邏輯劃分

按功能分

主鍵索引

一張表只能有一個主鍵索引，不允許重復、不允許為 NULL，使用關鍵字PRIMARY KEY定義；PRIMARY KEY的通?；贐樹（B-Tree）實現，本質上是特殊的唯一索引。

ALTER TABLE TableName ADD PRIMARY KEY(column_list);

唯一索引

數據列不允許重復，允許為 NULL 值；一張表可有多個唯一索引，索引列的值必須唯一，但允許有空值。如果是組合索引，則列值的組合必須唯一；一般使用UNIQUE INDEX定義

CREATE UNIQUE INDEX IndexName ON `TableName`(`字段名`(length));
# 或者
ALTER TABLE TableName ADD UNIQUE (column_list); 

普通索引

一張表可以創建多個普通索引，一個普通索引可以包含多個字段，允許數據重復，允許 NULL 值插入；

CREATE INDEX IndexName ON `TableName`(`字段名`(length));
# 或者
ALTER TABLE TableName ADD INDEX IndexName(`字段名`(length));

按使用分

按使用劃分其實就是單個列進行索引還是多個列組合索引。

• 單例索引：一個索引只包含一個列，一個表可以有多個單例索引。
• 組合索引：一個組合索引包含兩個或兩個以上的列。查詢的時候遵循 mysql 組合索引的 “最左前綴”原則，即使用 where 時條件要按照建立索引的時候字段的排列方式放置索引才會生效。MySQL中可以使用唯一索引和普通索引進行組合索引

-- 多列組合（普通索引）
CREATE INDEX <index_name> ON <table_name > (column1, column2, column3);
或
ALTER TABLE <table_name> ADD INDEX <index_name> (column1, column2,column3);

-- 多列組合（唯一索引）
CREATE UNIQUE INDEX <index_name> ON <table_name> (column1, column2,column3);
或
ALTER TABLE <table_name> ADD UNIQUE INDEX <index_name> (column1, column2,column3));

關于組合索引使用中的性能及使用原則，可直接跳至組合索引的使用原則

物理劃分

之所以說根據物理劃分是索引在物理存儲原理上的特點。而且主要是針對B+樹索引結構來講

簇的含義：為了提高某個屬性(或屬性組)的查詢速度，把這個或這些屬性(稱為聚簇碼)上具有相同值的元組集中存放在連續的物理塊。

聚簇索引

聚簇索引（clustered index）不是單獨的一種索引類型，而是一種數據存儲方式。這種存儲方式根據表的主鍵構造一棵B+樹，且B+樹葉子節點存放的都是表的行記錄數據時，該主鍵索引為聚簇索引。

在聚簇索引中，其數據文件本身就是索引文件。 樹的葉節點 data 域保存了完整的數據記錄。這個索引的 key 是數據表的主鍵，進行查詢時，根據搜索算法，在樹上找到葉子節點后，數據也一并找到。這種情況也就是常說的覆蓋索引。

注：每張表最多只能擁有一個聚簇索引

非聚簇索引

非聚簇索引又叫輔助索引或二級索引（在Mysql中primary key之外的均為輔助索引），與簇索引相反，數據和索引是分開的，B+Tree 葉節點的 data 域存放的是主鍵和該字段的值。在索引檢索的時候，首先按照 B+Tree 搜索算法搜索索引，如果指定的內容 存在，則取出其 data 域中的主鍵，然后再在聚簇索引（Primary Key 索引樹上再次搜索）。

假設我們針對user表查詢

SELECT sex,age FROM user WHERE name = '陳芳';

此時user表存在基于主鍵ID創建的聚簇索引，和基于name創建的非聚簇索引，那么查詢過程則是這樣的：

首先因為使用了name列進行等值查詢，此時會先使用Name索引的B+樹，進行搜索，當找到name為陳芳的葉子節點時，會拿到其ID，再回到基于ID的聚簇索引B+樹上進行基于ID=1的搜索，最終找到其葉子節點，拿到上面的性別和年齡，其中這種需要兩段使用索引的過程就是常說的回表查詢。 

雖然InnoDB和MyISAM存儲引擎都默認使用B+樹結構存儲索引，但是只有InnoDB的主鍵索引才是聚簇索引，InnoDB中的輔助索引以及MyISAM使用的都是非聚簇索引。

索引的使用

創建索引的原則

• 在經常需要搜索的列上，可以加快搜索的速度
• 在作為主鍵的列上，強制該列的唯一性和組織表中數據的排列結構
• 在經常用在連接（JOIN）的列上，這些列主要是一外鍵，可以加快連接的速度
• 在經常需要根據范圍（<，<=，=，>，>=，BETWEEN，IN）進行搜索的列上創建索引，因為索引已經排序，其指定的范圍是連續的
• 在經常需要排序（order by）的列上創建索引，因為索引已經排序，這樣查詢可以利用索引的排序，加快排序查詢時間；
• 在經常使用在WHERE子句中的列上面創建索引，加快條件的判斷速度。

數據類型對于索引的不同表現

VARCHAR類型

VARCHAR類型用于存儲可變長度的字符串。

• 前綴索引：由于VARCHAR類型的列可能很長，為了節省空間和提高效率，可以只為每個值的前幾個字符創建索引，稱為前綴索引。但是，前綴索引會降低索引的選擇性，可能需要掃描更多的行來找到匹配的記錄。
• 區分度：在選擇前綴長度時，應該考慮列的區分度。如果大多數行的前綴都相同，那么前綴索引的效果可能不佳。
• 索引效率：等值查詢、IN子句查詢等效率較高，VARCHAR類型的列在排序和比較時是按字典順序進行的，這可能會影響范圍查詢的性能。VARCHAR類型的索引在沒有使用函數或表達式的情況下性能較好，但如果在查詢中對字符串列使用了函數（如CONCAT、SUBSTRING等），索引可能失效，導致全表掃描。

數字類型

數字類型泛指數字相關類型，例如INT、FLOAT、Double等。

• 選擇性：整數類型的列通常具有很高的選擇性，這意味著索引中的值分布均勻，可以有效地減少查詢中需要檢查的行數。
• 索引效率：等值查詢、范圍查詢（>、<、BETWEEN等）效率較高，數字類型的索引在進行范圍查詢時查詢性能上通常優于字符串類型。

日期類型

DATETIME類型用于存儲日期和時間。

• 時區影響：在處理跨時區的數據時，需要注意時區轉換可能對索引的使用和查詢結果產生影響。
• 函數影響：如果查詢中使用了日期函數（如DATE_FORMAT），可能會導致索引失效
• 索引效率：DATETIME類型的列在進行等值查詢和范圍查詢時效率較高，因為日期和時間的比較操作非?？焖?。

其他

• 列的NULL值：如果列中包含NULL值，索引的行為可能會受到影響。例如，VARCHAR類型的列如果允許NULL值，可能會在索引中占用額外的空間。
• 列的默認值：默認值可能會影響索引的選擇性。例如，如果一個INT類型的列有一個默認值，那么很多行可能會有相同的默認值，這會降低索引的選擇性。
• 列的更新頻率：頻繁更新的列可能會使索引變得碎片化，從而影響索引的性能。因此，對于經常更新的列，可能需要定期重建索引。

組合索引的使用原則 

在MySQL中使用組合索引時，"最左前綴"原則決定了索引的使用方式和查詢優化的效果。這個原則指的是，MySQL會按照組合索引中列的順序，從左到右使用索引中的列。只有當索引的最左列被包含在查詢條件中時，索引才會被有效地使用。如果查詢條件中跳過了索引中的某個列，那么該列及其右邊的所有列都不會被用于索引查詢。

例如：將tb_flow_visit表的 源ip、目的ip、訪問時間 三個字段設置為組合索引（注意設置的順序）

ALTER TABLE tb_flow_visit ADD INDEX commIndies (sip, dip,visit_time);

順序優先

在組合索引中，MySQL會按照（源ip、目的ip、訪問時間）這個順序來匹配條件。如果WHERE子句中首先出現的是sip字段匹配相關的條件，那么索引才會被使用。

-- 有效索引查詢（全部匹配）
SELECT * FROM tb_flow_visit WHERE sip = '192.168.1.1' AND dip = '192.168.1.2' AND visit_time = '2023-08-01';

-- 有效索引查詢（部分匹配）
SELECT * FROM tb_flow_visit WHERE sip = '192.168.1.1' AND dip = '192.168.1.2';

不能跳過

如果你的查詢條件首先使用了dip（或者visit_time）而沒有包含sip，那么這個組合索引將不會被使用，因為違反了最左前綴原則。

-- 無效索引，不能跳過sip
SELECT * FROM tb_flow_visit WHERE  dip = '192.168.1.2' AND visit_time = '2024-08-01'; 

-- 無效索引，組合索引中，如過不按照索引順序，即便單獨使用其中任何一列也無效
SELECT * FROM tb_flow_visit WHERE dip = '192.168.1.2';
或
SELECT * FROM tb_flow_visit WHERE visit_time > '2024-08-01';;

部分匹配

如果WHERE子句中包含了從索引最左列開始的連續列，那么索引可以被部分使用。例如:使用了最左列sip的字段和visit_time字段，因此會有效使用sip列的索引，但不會使用dip和visit_time列的索引。

SELECT * FROM tb_flow_visit WHERE sip = '192.168.1.1' AND visit_time > '2024-08-01';

范圍查詢限制

在MySQL中，最左原則的范圍查詢限制是指在使用組合索引時，如果查詢條件中包含了范圍查詢（如>、<、BETWEEN、LIKE等），那么這個范圍查詢必須應用于組合索引的最左列或者緊挨著最左列的列（如果最左列是常量條件）。如果范圍查詢跳過了最左列或者在非最左列上使用，那么索引將不會被有效使用； 例如在最左列（sip）上使用了范圍查詢（如sip > '192.168.1.2'），那么后續的列仍然可以被索引使用，但最左列之后的列必須是等值查詢，不能是范圍查詢。

-- 無效索引
SELECT * FROM tb_flow_visit WHERE  sip > '192.168.1.2' AND dip > '192.168.2.1';
AND  visit_time = '2024-08-01';
-- 有效索引
SELECT * FROM tb_flow_visit WHERE  sip > '192.168.1.2' AND dip = '192.168.2.1' AND visit_time = '2024-08-01';