一、MySQL數據結構 InnoDB引擎 MySQL預設引擎是InnoDB引擎，這個引擎的主要特點是支持事務和行鎖，數據結構 2.1 二叉樹（二叉查找樹）二叉樹是一種特殊的樹，二叉樹中每個節點的度都不能大於2，就是說每個節點最多只能有左右兩個子節點當我們像二叉查找樹儲存數據的時候，是安裝從大到 ...

一、MySQL數據結構

InnoDB引擎

MySQL預設引擎是InnoDB引擎，這個引擎的主要特點是支持事務和行鎖，

數據結構

2.1 二叉樹（二叉查找樹）

二叉樹是一種特殊的樹，二叉樹中每個節點的度都不能大於2，就是說每個節點最多只能有左右兩個子節點
當我們像二叉查找樹儲存數據的時候，是安裝從大到小（或從小到大）的順序保存的，這樣有可能會形成一個單項鏈表的結構，搜索性能就會大打折扣。

為瞭解決平衡避免出現這種鏈表的結構，所以才有了平衡二叉樹

2.2 平衡二叉樹

平衡二叉樹就能解決上面的問題

(1)非葉子節點最多擁有兩個子節點
(2)非葉子節值大於左邊子節點、小於右邊子節點;
(3)樹的左右兩邊的層級數相差不會大於1,
(4)沒有值相等重覆的節點

平衡二叉樹會通過左旋右旋來平衡二叉樹，避免變成單向鏈表結構，但過度要求平衡，會頻繁的左右旋，
所以後面就出現了紅黑樹

2.3 紅黑樹

紅黑樹只是減少左右旋，本身還是會左旋和右旋

性質1：每個節點要麼是紅色，要麼是黑色。
性質2：根節點是黑色。
性質3：每個葉子節點（NIL節點，也就是 NULL 節點）是黑色。
性質4：如果一個節點是紅色的，則它的兩個子節點都是黑色的（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）。
性質5：從任一節點到其每個葉子的所有簡單路徑都包含相同數量的黑色節點。

平衡性：
- 紅黑樹通過上述性質確保了樹的高度保持在 O(log n)，其中 n 是樹中的節點數。
- 這種性質保證了紅黑樹的操作（查找、插入、刪除）的時間複雜度為 O(log n)。
插入操作：
- 插入新節點時，新節點預設著色為紅色。
- 插入後，如果破壞了紅黑樹的性質，需要通過旋轉和重新著色來恢復性質。
- 可能的旋轉操作包括左旋、右旋、左右旋和右左旋。
刪除操作：
- 刪除節點可能導致紅黑樹失去平衡。
- 刪除後，需要通過旋轉和重新著色來恢復性質。
- 刪除操作可能涉及複雜的顏色調整和旋轉。
旋轉操作：
- 左旋（Left Rotation）：如果需要將一個節點的右子節點提升到更高的位置，可以進行左旋。
- 右旋（Right Rotation）：如果需要將一個節點的左子節點提升到更高的位置，可以進行右旋。
- 左右旋（Left-Right Rotation）：先對節點的左子節點進行左旋，然後對節點本身進行右旋。
- 右左旋（Right-Left Rotation）：先對節點的右子節點進行右旋，然後對節點本身進行左旋。

2.4 B-Tree（平衡多路查找樹）

每一個節點都儲存完整的一條數據，這是和B+Tree最明顯的區別，對於範圍查詢效率不高。
InnoDB存儲引擎中有頁（Page）的概念，頁是其磁碟管理的最小單位。InnoDB存儲引擎中預設每個頁的大小為16KB（16384/1024），InnoDB在把磁碟數據讀入到記憶體時會以頁為基本單位

假如說：每個磁碟塊的大小是1k（一個指針+一個數據節點是1k），那麼一頁就是有16個磁碟塊，如果每次載入一頁，也有16個指針，而且每個指針指向一個磁碟塊（第二層），那麼對於一個三層的b-樹來說。能存儲的節點數就是：16X16X16 = 4096

當需要查詢的數據很多時，也就是十萬百萬級別的時候，B-Tree結構對於查詢的效率就不怎麼管用了，因為這個時候樹的層級會很高，當存儲的數據量很大時同樣會導致B-Tree的深度較大，增大查詢時的磁碟I/O次數。
所以後面的B+Tree進一步優化這件事。

2.5 B+Tree

和B-Tree的主要區別是B+Tree的所有數據存儲在葉子結點中，非葉子節點只存儲鍵值信息和指針，而有數據的葉子結點會形成一個雙向鏈表的結構，可以範圍查詢。

InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型為INT（占用4個位元組）或BIGINT（占用8個位元組），指針類型也一般為4或8個位元組，也就是說一個頁（B+Tree中的一個節點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值，為方便計算，這裡的K取值為1000。也就是說一個深度為3的B+Tree索引可以維護1000 * 1000 * 50(最後一層每個磁碟塊存多少數據節點，假設是50個) = 5千萬條記錄。深度一般是三到四層

特點：

所有的葉子結點中包含了全部關鍵字的信息，非葉子節點只存儲鍵值信息，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序鏈接，所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。 (而B樹的非終節點也包含需要查找的有效信息)
所有葉子節點之間都有一個鏈指針。
數據記錄都存放在葉子節點中。

二、索引

什麼是索引？

資料庫管理系統（DBMS）中用於加快數據檢索速度的一種數據結構，InnoDB用的是B+Tree的結構
特點：

占用磁碟空間
大大提高查詢效率，減少磁碟IO
降低增刪改的效率

索引的類型

聚簇索引（Clustered Index）：數據按照索引順序存儲，每個表只能有一個聚簇索引。
非聚簇索引（Nonclustered Index）：數據和索引分開存儲，一個表可以有多個非聚簇索引。
唯一索引（Unique Index）：保證索引中的鍵值唯一。
全文索引（Full-text Index）：用於全文搜索，支持複雜的內容搜索

聚簇索引和非聚簇索引

聚簇索引，每個節點都存有完整的數據
非聚簇索引，只存了Key和指針和ID

回表和索引覆蓋：
回表：當查詢一個或一些數據的時候，如：select * from table where name = Joker 的時候，假設索引欄位是 name，非聚簇索引查到了名字，但需要的是全部的數據，這時候和根據查到ID進行聚簇索引查詢，這就是回表。
索引覆蓋，以上，如果是 select name from table where name = Joker，需要的數據剛好可以通過非聚簇索引查詢，不需要回表，這時候就是索引覆蓋。（所以MySQL優化中有一個要求是：避免使用select *）

索引失效

可以使用Explain來查詢是否使用了索引
避免索引失效對於提高資料庫查詢性能至關重要。以下是幾種常見的方法來確保索引的有效使用：

1. 最左首碼原則

全值匹配：確保 WHERE 子句中的條件與索引列的順序相匹配。
不要跳過索引列：如果索引是複合索引（多個列組成的索引），查詢時應該從最左邊的列開始，依次向右進行匹配，不能跳過中間的列。

2. 避免在索引列上進行操作

不要在索引列上使用函數：例如 WHERE UPPER(column) = 'value'。
不要在索引列上進行表達式操作：例如 WHERE column * 2 = 10。
避免類型轉換：確保查詢中的常量與索引列的數據類型一致。

3. 範圍條件後的列不可用

如果使用了範圍條件（如 <, <=, >, >=, BETWEEN, LIKE 開頭的模式匹配等），則在範圍條件之後的索引列無法被使用。

4. 使用覆蓋索引

覆蓋索引：當索引包含了所有需要查詢的欄位時，可以避免回表查詢（即不需要再從主鍵索引中查找數據）。
減少 SELECT * 的使用：明確指定所需的列，而不是使用 SELECT *。

5. LIKE 語句的使用

避免以通配符開頭：如果使用 LIKE '%value%'，則索引可能失效。但如果使用 LIKE 'value%' 或 LIKE '%value'，則索引仍可有效利用。

6. 數據類型的匹配

確保索引列和查詢中的值的數據類型一致，避免隱式類型轉換。

7. 避免使用 NOT IN 和 NOT EXISTS

使用 NOT IN 或 NOT EXISTS 可能會導致索引失效。可以嘗試使用 LEFT JOIN 或 NOT EXISTS 結合子查詢的方式代替。

8. 選擇合適的數據類型

為索引列選擇合適的數據類型，尤其是當有多種數據類型可以選擇時，選擇占用空間較小的數據類型可以節省存儲空間，提高索引的效率。

9. 維護索引

定期檢查和優化索引，例如使用 ANALYZE TABLE 和 OPTIMIZE TABLE 命令。

10. 避免使用 SELECT *

明確列出需要查詢的欄位，減少不必要的數據傳輸。

11. 使用全文索引

對於全文搜索，使用全文索引（如 FULLTEXT 索引）。

12. 限制使用 OR

當使用 OR 時，確保至少有一個條件能夠使用有效的索引。

通過遵循以上原則，可以有效地避免索引失效的問題，從而提升資料庫查詢的性能。

MySQL數據結構和索引