深入理解Mysql索引 - tw511教學網

在資料庫中，最常用的SQL操作之一就是SELECT語句，它負責資料的檢索。而在SELECT語句背後，與索引的互動密不可分。為了優化資料庫效能和加快查詢速度，開發者們往往優先考慮調整索引。

讓我們深入瞭解索引的背後故事。這篇文章將從什麼是索引，索引的分類，索引的底層資料資料結構，跟大家一起來學習索引。

1.什麼是索引

在資料庫中，索引是一種資料結構，它可以加快資料庫表中資料的檢索速度。當在資料庫表中建立索引時，資料庫管理系統會根據指定的欄位或列建立一個索引結構，以便在查詢資料時可以更快地找到匹配的記錄，而不必逐條掃描整個表。

Mysql官網是這樣描述的：索參照於快速查詢具有特定列值的行。如果沒有索引，MySQL 必須從第一行開始，然後讀取整個表以查詢相關行。表越大，成本就越高。如果表有相關列的索引，MySQL 可以快速確定要在資料檔案中間查詢的位置，而無需檢視所有資料。這比順序讀取每一行要快得多。

2.索引的分類

按照資料結構分類

B+樹索引：B+樹索引是一種常見的索引型別，它使用B+樹資料結構進行組織，適用於各種查詢條件，包括精確匹配和範圍查詢。
Hash索引：Hash索引使用雜湊演演算法將索引值對映到雜湊表中的槽位，適用於精確匹配查詢，不支援範圍查詢。
Full-text索引：Full-text索參照於對文字欄位進行全文搜尋，支援模糊匹配和關鍵詞搜尋。

按照索引在資料庫中的角色分類

聚簇索引（也稱為聚集索引）：聚簇索引是按照索引列的順序直接組織表中的資料。在InnoDB儲存引擎中，主鍵索引就是聚簇索引，用於標識表中每一行，並決定了表中資料的物理儲存順序。
二級索引（也稱為輔助索引）：二級索引是基於聚簇索引之外的其他列構建的索引，包含索引列的值和對應的主鍵值，用於加快特定查詢的速度。

按照索引的特性分類

主鍵索引（Primary Key Index）：用於標識表中每一行的索引，每張表只能有一個主鍵索引。
唯一索引（Unique Index）：確保索引列的值是唯一的，不允許重複值。
普通索引（Normal Index）：最基本的索引型別，允許出現重複值和NULL值。
字首索引（Prefix Index）：對索引列的字首進行索引，節省儲存空間但可能犧牲查詢精確性和效能。

其他索引分類

稀疏索引：稀疏索引是一種針對包含大量重複值的列的索引。它只儲存索引列中不重複的值和對應的指標，以減少索引的儲存空間。

3.索引的資料結構分析

從資料結構的角度來看來可以當做索引的資料結構有很多種例如,二元樹，紅黑樹，B-樹，B+樹，Hash,為什麼MySQL會選擇B+樹來當做預設的索引呢。這裡推薦大家使用Data Structure Visualization來對資料結構進行分析。

Data Structure Visualization https://www.cs.usfca.edu/~galles/visualization/about.html

首先我們來看二元樹，二元樹是一種有序的樹狀資料結構，每個節點最多有兩個子節點：左子節點和右子節點。並且左子樹的節點值小於等於父節點的值，右子樹的節點值大於等於父節點的值。那麼當二元樹作為索引結構時，假如我們的id是1,2,3,4,5,6，連續的id 那麼二元樹形成的索引結構如下圖所示，

這種非平衡二元樹，在出現資料連續的情況，會使得二元樹變成連結串列。這種情況將嚴重影響查詢效能，使得查詢效率降低為O(n)，其中n是資料的數量，而不再是O(log n)。

這種連結串列化的二元樹通常稱為退化的二元樹（Degenerate Binary Tree），它的高度和資料量成正比，而不再保持對數級別的高效性。退化的二元樹的查詢時間複雜度退化為線性搜尋，會使得索引的意義幾乎喪失，造成資料庫查詢效率極低。

為了避免退化的二元樹情況，通常採用平衡二元樹作為索引資料結構，如AVL樹和紅黑樹。

紅黑樹的五個性質：

每個節點要麼是黑色，要麼是紅色，這是紅黑樹的最基本性質。
根節點必須是黑色，這確保了樹的平衡性質。
葉子節點是指為空(NIL或NULL)的節點，它們也被認為是黑色的。這樣做是為了簡化紅黑樹的定義和實現。
紅黑樹的這個性質確保了沒有兩個相鄰的紅色節點，防止出現連續的紅色節點，保持了樹的平衡。
從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點,它確保了在最壞情況下，紅黑樹的高度不會超過其節點數的兩倍，從而保持了樹的平衡效能。

通過這些性質，紅黑樹保證了在插入和刪除節點時通過旋轉和顏色調整來維護樹的平衡，從而保持了樹的高度在對數級別，保證了較好的查詢效能和資料插入、刪除效能。

紅黑樹雖然解決了二元樹平衡性的問題，但在某些情況下，它的樹高仍然會隨著資料量的增加而增長，使得樹的高度不斷增大，從而導致查詢效能下降。這是因為紅黑樹的自平衡特性，在插入和刪除節點時，紅黑樹會通過旋轉和顏色調整來保持樹的平衡。這使得紅黑樹在大部分情況下可以保持相對平衡，但在某些特定情況下，可能無法避免樹的高度增加。

通過二元樹和紅黑樹展示，我們可以看出，隨著樹的高度的增加從而導致了查詢的時間複雜的增加；在資料庫索引中，樹的高度直接影響了尋找資料時所需的磁碟IO次數。樹的高度越低，查詢資料所需的磁碟IO次數就越少，從而提高了查詢的效能。因此我們需要關注能夠減少磁碟IO次數，優化資料存取效率的資料結構，B樹和B+樹都是多叉平衡搜尋樹，它們的設計目標正式如此。

B樹（B-tree）：B樹是一種平衡的多叉搜尋樹，它的每個節點可以儲存多個資料項（通常稱為鍵或索引值）。B樹的每個節點有多個子節點，子節點的個數稱為B樹的階（order）。B樹的特點是每個節點的資料項按照鍵的大小有序排列，同時保持整個樹的平衡，即所有葉子節點到根節點的高度差不超過1。

B+樹（B+ tree）：B+樹是在B樹的基礎上做了一些改進，它也是一種平衡的多叉搜尋樹。與B樹不同的是，B+樹的非葉子節點僅用於索引導航，不儲存資料，而所有的資料項都儲存在葉子節點中。葉子節點形成一個有序連結串列，可以更高效地進行範圍查。

在MySQL中，對B+樹進行了改造，讓葉子節點的單向連結串列變成了雙向連結串列，這是為了更好地支援範圍查詢。B+樹的葉子節點構成一個雙向連結串列，這使得範圍查詢時更加高效。通過雙向連結串列，可以在葉子節點之間快速地前進或後退，而不需要回到根節點重新開始查詢。這種雙向連結串列的設計對於資料庫查詢和範圍查詢非常有利，特別是對於一些大規模的資料庫查詢，可以極大地提高查詢效率。另外，MySQL中的B+樹通常採用頁分裂和頁合併來維護樹的平衡。當插入資料或刪除資料時，可能導致葉子節點的空間不足或過多，這時候MySQL會進行頁分裂或頁合併的操作，確保樹的平衡性。

那為什麼MySQL最終選擇了B+樹而沒有選擇B樹呢？主要原因有四點：

資料儲存方式

B樹的非葉子節點既儲存索引鍵值，又儲存實際資料。這意味著在B樹的每個節點中，既包含索引資訊，又包含資料資訊。這樣的設計使得B樹在查詢特定鍵值時，不僅可以找到索引位置，還可以直接獲取資料，因為資料也儲存在非葉子節點中。

B+樹的非葉子節點僅儲存索引鍵值，而所有的資料項都儲存在葉子節點中。這使得B+樹的非葉子節點更加緊湊，只用於索引導航，不佔用額外的空間來儲存資料。這樣的設計使得B+樹在查詢特定鍵值時，只需遍歷索引層級，不需要在非葉子節點和葉子節點之間跳轉，從而減少了IO操作。

         [20, 40, 60]
       /      |     \
[5, 10]   [25, 30]  [45, 50, 55, 58]
假設我們有一個B樹的節點最大容量為3的情況。
在這個B樹中，每個節點儲存的鍵值數量不定，但都在一個範圍內。每個非葉子節點既儲存索引鍵值，又儲存實際資料。
例如，節點[20, 40, 60]包含鍵值20、40和60，並且包含對應的子節點的指標。這樣的設計使得B樹在查詢特定鍵值時，不僅可以找到索引位置，還可以直接獲取資料。

          [40]
       /    |    \
[5, 10, 20]-> [30, 35] ->[45, 50, 55, 58]
假設我們有一個B+樹的節點最大容量為3的情況。
在這個B+樹中，每個節點儲存的索引鍵值數量更多，相比於B樹，它具有更高的空間利用率。每個非葉子節點僅儲存索引鍵值，而所有的資料項都儲存在葉子節點中。
例如，節點[40]僅包含鍵值40，並且包含指向葉子節點的指標。這使得B+樹的非葉子節點更加緊湊，只用於索引導航，不佔用額外的空間來儲存資料。

範圍查詢效能

由於B+樹的所有資料都儲存在葉子節點上，並且葉子節點形成有序連結串列，使得範圍查詢時具有更好的效能。B樹的非葉子節點也儲存資料，範圍查詢時需要在不同的層級之間進行跳轉，增加了IO操作次數，影響了範圍查詢的效能。

        [20, 40, 60]
       /      |     \
[5, 10]   [25, 30]  [45, 50, 55, 58]
假設我們要進行鍵值在10到30之間的範圍查詢。範圍查詢需要在不同的層級之間跳轉，增加了IO操作。

               [40]
           /    |    \
[5, 10, 20]-> [30, 35] ->[45, 50, 55, 58]
範圍查詢只需在葉子節點之間遍歷有序連結串列，不需要在不同的層級之間跳轉，減少了IO操作。

空間利用率

B樹的每個節點儲存的關鍵字數量不固定，通常在一個範圍內。因為每個節點儲存的關鍵字數量不定，所以可能出現節點空間利用率較低的情況。這可能導致B樹的層級較多，使得樹的高度相對較高，增加了磁碟IO操作次數。

B+樹的每個節點儲存的索引鍵值更多，相比於B樹，它具有更高的空間利用率。因為B+樹的非葉子節點不儲存資料，只儲存索引鍵值，而所有的資料項都儲存在葉子節點中。這樣的設計使得B+樹的非葉子節點更加緊湊，有更多的空間來儲存索引，從而減少了樹的高度，提高了查詢效能。

範圍查詢和排序操作

B+樹的葉子節點形成有序連結串列，使得範圍查詢和排序操作更加高效。例如，對於範圍查詢，可以通過遍歷有序連結串列來獲得所需的資料，而不需要回溯到非葉子節點。

最後再來講一下hash索引

當使用雜湊索引時，資料庫會將索引鍵值通過雜湊函數計算得到一個雜湊值，然後將雜湊值對映到特定的儲存位置。雜湊索引是一種將索引鍵值與儲存位置直接對映的資料結構，適用於等值查詢，即根據精確的索引鍵值查詢對應的資料行。

雜湊索引的特性：

高效的等值查詢：由於雜湊索引直接通過雜湊值查詢儲存位置，等值查詢非常高效，時間複雜度為O(1)。在索引資料量較大的情況下，雜湊索引通常比B+樹索引更快。
不支援範圍查詢：由於雜湊索引的特性是將索引鍵值對映到一個特定的儲存位置，而不是形成有序結構，所以不支援範圍查詢，無法用於處理區間查詢或排序操作。
衝突處理：由於雜湊函數可能將不同的索引鍵值對映到相同的雜湊值，這就產生了雜湊衝突。資料庫需要採用衝突解決策略，常見的解決方法是開鏈法（Chaining）或開放地址法（Open Addressing）。

雜湊索引的應用場景：雜湊索引適用於等值查詢非常頻繁，而範圍查詢較少的場景。例如，在處理雜湊ID（如使用者ID、訂單號等）時，雜湊索引可以提供非常高效的查詢速度。但是，由於不支援範圍查詢和排序操作，雜湊索引在涉及範圍查詢或排序的場景中就不適用。

需要注意的是，雜湊索引對於資料庫表的增刪改操作可能會引發大量的資料遷移和重建，因此在選擇索引型別時，需要綜合考慮實際應用需求、查詢型別和資料更新頻率。在MySQL中，常用的索引型別是B+樹索引，因為它適用於各種查詢型別，支援範圍查詢和排序操作，並且可以滿足大部分應用場景的需求。

4.索引的儲存位置和檔案型別

mysql 的資料存在data 目錄下,根據不同的引擎來構建成不同的檔案型別。

InnoDB儲存引擎：在InnoDB中，表的資料和索引都儲存在.ibd檔案中。如果您在構建表時使用的引擎是InnoDB，則會生成.frm和.ibd檔案。InnoDB使用B+樹的資料結構來組織資料，而且使用聚簇索引。聚簇索引的葉子節點儲存整行資料，因此資料的物理儲存順序與主鍵的邏輯順序相同。這使得InnoDB的聚簇索引在某些情況下具有更好的效能，特別是對於範圍查詢和基於主鍵的查詢。

在InnoDB儲存引擎中，構建主鍵索引和非主鍵索引的葉子節點儲存方式是不同的，這在查詢時會產生不同的影響。

主鍵索引：對於構建在主鍵上的索引，其葉子節點儲存的是資料行的實際資料和主鍵值。這意味著主鍵索引是覆蓋索引（Covering Index），可以直接通過索引就能獲取到查詢所需的資料，無需回表查詢。

非主鍵索引：對於構建在非主鍵列上的索引，其葉子節點儲存的是索引列的鍵值和對應的主鍵值。在進行查詢時，首先通過非主鍵索引找到對應的主鍵值，然後再根據主鍵值回表查詢，獲取到實際的資料。這就是所謂的"回表查詢"，在查詢非主鍵列的資料時，需要額外的I/O操作去獲取實際的資料。

例子：假設我們有一個表 students，其中有主鍵 id 和非主鍵索引 name_index，索引結構如下：

主鍵索引： [1: Alice] [2: Bob] [3: Charlie] [4: David] ... 
非主鍵索引： [Alice: 1] [Bob: 2] [Charlie: 3] [David: 4] ...

如果我們執行以下查詢：

SELECT * FROM students WHERE id = 2;

由於主鍵索引是覆蓋索引，查詢引擎可以直接從主鍵索引中獲取到id=2對應的資料行。而如果我們執行以下查詢：

SELECT * FROM students WHERE name = 'Bob';

由於name是非主鍵列，查詢引擎首先會通過name_index找到name='Bob'對應的主鍵值（在本例中是id=2），然後再根據主鍵值回表查詢，獲取到實際的資料行。

因此，在InnoDB中，對於非主鍵列的查詢可能會產生回表查詢的額外開銷，而對於主鍵列的查詢則可以直接利用主鍵索引的覆蓋索引特性，避免回表查詢，提高查詢效能。

MyISAM儲存引擎：在MyISAM中，表的資料和索引分別儲存在.myd和.myi檔案中。如果您在構建表時使用的引擎是MyISAM，則會生成.frm、.myd和.myi檔案。MyISAM也使用B+樹的資料結構來組織資料，但是它使用非聚簇索引。非聚簇索引的葉子節點儲存的是主鍵值的對映指標和地址，而不是真正的資料行。在MyISAM中，資料的物理儲存順序與主鍵的邏輯順序不一定相同。這意味著在MyISAM中，對於範圍查詢或基於主鍵的查詢，可能需要進行更多的磁碟I/O操作，因為資料可能不連續儲存。

InnoDB的聚簇索引和MyISAM的非聚簇索引之間的差異在於資料的物理儲存方式。聚簇索引將資料儲存在葉子節點中，使得相關資料緊湊儲存，而非聚簇索引則需要進行額外的指標查詢來定位真正的資料行。因此，在選擇儲存引擎時，要考慮資料存取模式、效能需求和特定查詢型別，以使得索引能夠更好地滿足您的應用需求。

聯合索引分析

當一個索引由多個列組成，我們稱之為聯合索引（Composite Index）或複合索引。聯合索引允許在多個列上進行查詢，而不僅限於單獨的列，這樣可以更高效地支援涉及多個列的查詢條件。

聯合索引如何排序

聯合索引的排序方式是按照聯合索引的各個列順序進行排序。在建立聯合索引時，索引的第一個列按照其自身的排序規則進行排序，如果存在相同的值，則根據索引的第二個列排序，依此類推。這樣可以形成一個多級排序的結構，以便快速地定位到滿足查詢條件的資料行。

假設有一個表 products，其中包含聯合索引 (category, brand, price)，並且索引的各個列的排序方式分別如下：

聯合索引 (category, brand, price) 排序：
(Computers, Dell, 1000) 
(Computers, HP, 800) 
(Computers, Lenovo, 900) 
(Electronics, Samsung, 600) 
(Electronics, Sony, 700) 
(Furniture, Ikea, 300) 
(Furniture, Ashley, 400) 
(Furniture, Wayfair, 500) ...

在這個聯合索引中，首先按照category列的排序順序進行排序，如果category相同，則按照brand列的排序順序進行排序。如果category和brand都相同，則按照price列的排序順序進行排序。這樣的多級排序結構可以快速定位滿足查詢條件的資料行。

例如，如果執行以下查詢：

SELECT * FROM products WHERE category = 'Computers' AND brand = 'Dell';

由於查詢條件涉及到聯合索引的前兩個列 category 和 brand，資料庫引擎可以直接使用聯合索引快速定位到滿足條件的資料行，而無需掃描整張表。

然而，如果執行以下查詢：

SELECT * FROM products WHERE brand = 'Dell' AND price < 1000;

由於查詢條件中的列 brand 不是聯合索引的第一個列，而是第二個列，所以這個查詢無法充分利用聯合索引的排序順序。在這種情況下，資料庫引擎可能無法使用聯合索引，而需要進行全表掃描來查詢滿足條件的資料行。

因此，建立聯合索引時，要根據實際查詢需求和資料的存取模式，選擇合適的列順序，以提高查詢效能。如果查詢條件中的列與聯合索引的字首列匹配，索引可以有效利用，但如果與後面的列匹配，索引的效率可能會降低。

聯合索引的特性：

覆蓋索引：當查詢涉及到的列都包含在聯合索引中，並且索引的列順序與查詢條件的順序一致時，聯合索引就可以成為覆蓋索引，從而避免回表查詢，提高查詢效能。
索引選擇性：聯合索引的選擇性是指索引中不同列的唯一組合數量。選擇性越高，索引在過濾資料時可以更快地定位到目標行。通常情況下，選擇性越高，索引的效率越高。
最左字首匹配：對於聯合索引，最左字首匹配是指索引從最左邊的列開始匹配查詢條件。在某些情況下，只有最左邊的列被用於查詢時，索引才會被利用。如果查詢涉及到索引的連續部分，但不是從最左邊開始，那麼聯合索引的效率會降低。

聯合索引的應用場景：聯合索引適用於多列組合查詢，特別是在涉及到多個列的過濾條件時，可以顯著提高查詢效能。例如，對於包含"性別"和"年齡"兩列的表，如果查詢需要同時過濾這兩個條件，可以建立一個聯合索引來加速查詢。聯合索引也適用於覆蓋查詢，當查詢需要的列都包含在聯合索引中時，可以避免回表查詢，提高查詢效率。

雖然聯合索引可以提高查詢效能，但也需要權衡索引的大小和更新的開銷。在建立聯合索引時，需要考慮表的查詢頻率、更新頻率、索引選擇性和查詢的多樣性等因素，綜合評估索引的效率和維護成本。