04_深入淺出索引（上）

‍

索引的概念

索引的概念：索引是一種數據結構，用於提高資料庫查詢效率。就像一本書的目錄一樣，索引可以幫助資料庫在大量數據中快速找到需要的數據，減少查詢時間和資源消耗。

除了提高查詢效率，索引還可以幫助資料庫實現唯一性約束、主鍵約束和外鍵約束等數據完整性約束。

例如，在一個用戶表中，我們可以使用用戶ID作為主鍵，併在ID列上創建一個唯一索引，以保證每個用戶ID都是唯一的。

‍

常見索引模型

常見索引模型：索引模型是指索引的數據結構和組織方式。常見的索引模型有哈希表、有序數組和搜索樹等。

哈希表：哈希表是一種將鍵映射到值的數據結構，它通過哈希函數將鍵轉換為數組的下標，然後將值存儲在該下標處。

哈希表適用於等值查詢場景，例如在一個存儲用戶信息的表中，我們可以使用用戶ID作為哈希表的鍵，來快速查找某個用戶的信息。

有序數組：有序數組是一種按照元素大小順序排列的數組，它適用於等值查詢和範圍查詢場景。

例如，在一個按照身份證號排序的用戶表中，我們可以使用二分法快速查找某個身份證號對應的用戶信息。但是，有序數組的更新成本較高，適用於靜態存儲引擎。

搜索樹：搜索樹是一種按照元素大小順序組織的樹形結構，它適用於等值查詢和範圍查詢場景。

例如，在一個按照用戶ID排序的用戶表中，我們可以使用二叉搜索樹快速查找某個用戶ID對應的用戶信息。但是，搜索樹的查詢效率高，但寫入和更新成本高，不適用於大規模數據存儲。

擴充例子：在一個電商網站的訂單表中，我們可以使用訂單ID作為哈希表的鍵，來快速查找某個訂單的信息。在一個按照訂單時間排序的訂單表中，我們可以使用二分法快速查找某個時間段內的訂單信息。在一個按照商品價格排序的商品表中，我們可以使用B樹來快速查找某個價格區間內的商品信息。

二叉樹雖然是搜索效率最高的，但是實際上大多數的資料庫存儲卻並不使用二叉樹，因為索引不僅存在記憶體中，還要寫入磁碟。

為了讓查詢儘量少地讀磁碟，我們需要讓查詢過程訪問儘量少的數據塊。因此，我們應該使用“N叉”樹來代替二叉樹。在“N叉”樹中，“N”的大小取決於數據塊的大小。

以InnoDB的一個整數欄位索引為例，這個“N”大約是1200。當這棵樹高為4時，就可以存儲1200的3次方個值，這已經達到了17億。考慮到樹根的數據塊總是在記憶體中，一個10億行的表上一個整數欄位的索引，查找一個值最多只需要訪問3次磁碟。實際上，樹的第二層也有很大概率在記憶體中，那麼訪問磁碟的平均次數就更少了。

擴充闡述：在實際的資料庫應用中，磁碟I/O是非常耗時的操作。因此，我們需要儘量減少磁碟I/O的次數，以提高資料庫的查詢效率。為了實現這個目標，資料庫存儲引擎通常會採用B樹、B+樹、R樹等數據結構來實現索引。這些數據結構都是基於“N叉”樹的結構，能夠有效地減少磁碟I/O的次數，提高查詢效率。

例如，在一個電商網站的商品表中，我們可以使用商品價格作為B+樹的鍵，來快速查找某個價格區間內的商品信息。B+樹在葉子節點上保存了所有數據記錄的指針，而非像B樹那樣在每個節點上都保存數據記錄，因此能夠減少磁碟I/O的次數，提高查詢效率。

總結：為了提高資料庫的查詢效率，我們需要選擇合適的索引模型，並採用相應的數據結構來實現索引。在選擇數據結構時，需要考慮具體的查詢場景和存儲引擎特點。常見的索引模型有哈希表、有序數組和搜索樹等，而常用的數據結構有B樹、B+樹、R樹等。通過選擇合適的索引模型和數據結構，可以有效地提高資料庫的查詢效率，降低磁碟I/O的次數，從而提升資料庫的整體性能。

‍

資料庫底層存儲的核心就是基於這些數據模型的。每碰到一個新資料庫，我們需要先關註它的數據模型，這樣才能從理論上分析出這個資料庫的適用場景。

‍

B 樹和 B+ 樹

B樹和B+樹都是多路搜索樹，是一種常用的數據結構，在資料庫、文件系統等領域廣泛應用。它們不是二叉樹，而是多叉樹。

B樹和B+樹的主要區別在於它們的索引結構和葉子節點的存儲方式不同。B樹的每個節點都包含鍵值和指向子節點的指針，而B+樹的非葉子節點只包含鍵值和指向子節點的指針，而所有的數據都存儲在葉子節點中。

B樹的搜索過程比較複雜，因為需要在非葉子節點和葉子節點之間不斷切換，而B+樹的搜索過程更加簡單，因為只需要在葉子節點中進行搜索。此外，B+樹的葉子節點是通過鏈表相連的，可以方便地進行範圍查詢和遍歷。

因此，B+樹通常比B樹更適合在資料庫中使用，因為它能夠更快地進行範圍查詢和遍歷。但是，在某些場景下，B樹也可能比B+樹更適合使用，例如需要快速插入和刪除數據的場景。

‍

InnoDB 的索引模型

在InnoDB中，表都是根據主鍵順序以索引的形式存放的，這種存儲方式的表稱為索引組織表。

InnoDB 使用的是 B+ 樹索引模型，所以數據都是存儲在 B+ 樹中的，每一個索引在 InnoDB 裡面對應一棵 B+ 樹。

索引類型分為主鍵索引和非主鍵索引。

• 主鍵索引的葉子節點存的是整行數據。在 InnoDB 里，主鍵索引也被稱為聚簇索引（clustered index）。
• 非主鍵索引的葉子節點內容是主鍵的值。在 InnoDB 里，非主鍵索引也被稱為二級索引（secondary index）。

舉個例子來說，假設我們有一個學生表，其中主鍵為學生ID。如果我們要查詢學號為1001的學生的所有信息，如果使用主鍵索引，則只需要搜索ID這棵B+樹，而如果使用非主鍵索引，則需要先搜索學號這棵B+樹得到ID的值為1001，再到ID索引樹搜索一次，這個過程稱為回表。

因此，使用主鍵索引查詢可以減少一次搜索，提高查詢效率。

在應用中我們應該儘量使用主鍵查詢，以減少查詢時間和提高性能。

但是，在實際使用中，我們也需要根據具體情況來選擇使用哪種索引類型。例如，如果我們需要查詢學生的所有信息，而不僅僅是學號，那麼使用主鍵索引就無法滿足我們的需求，這時候就需要使用非主鍵索引。

InnoDB的索引模型是資料庫中非常重要的一個概念，不同的索引類型在查詢效率和使用場景上都有著不同的優缺點。我們需要根據具體需求來選擇使用哪種索引類型，以提高資料庫的性能和效率。

‍

索引維護

索引維護是資料庫中非常重要的一部分，它確保了數據的快速查詢和排序。

在B+樹中，為了維護索引有序性，在插入新值的時候需要做必要的維護。

這個過程中，當插入的數據頁已經滿了，就需要進行頁分裂操作。這個過程會申請一個新的數據頁，並將部分數據挪動過去，影響了性能和數據頁的利用率。

不過，有分裂就有合併。當相鄰兩個頁由於刪除了數據，利用率很低之後，會將數據頁做合併，這個過程可以認為是分裂過程的逆過程。

另外，對於自增主鍵的使用場景，我們需要分析哪些場景下應該使用自增主鍵，而哪些場景下不應該。

自增主鍵的插入數據模式，是遞增插入的場景，每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。

而有業務邏輯的欄位做主鍵，則往往不容易保證有序插入，這樣寫數據成本相對較高。

此外，從存儲空間的角度來看，如果用身份證號等字元串類型的欄位做主鍵，那麼每個非主鍵索引的葉子節點上都是主鍵的值，占用的空間較大。因此，自增主鍵往往是更合理的選擇。

但是，對於只有一個索引且必須是唯一索引的場景，可以直接將這個索引設置為業務欄位做主鍵，避免每次查詢需要搜索兩棵樹。

假設你在設計一個訂單系統，其中包含訂單的ID、用戶ID、商品ID、數量、價格等信息。如果你需要在該系統中快速查找某個訂單的信息，可以在訂單ID欄位上建立一個唯一索引，這樣就可以快速查找到該訂單的信息。但是，如果你需要根據用戶ID或商品ID等信息進行查詢，那麼就需要在這些欄位上建立索引，以保證查詢的速度和效率。

在這種情況下，如果使用自增主鍵作為主鍵，可以保證數據的有序插入和查詢，提高了查詢效率。每次插入一條新記錄，都是追加操作，都不涉及到挪動其他記錄，也不會觸發葉子節點的分裂。此外，自增主鍵的數據類型通常為整型，占用的存儲空間相對較小，可以節省存儲空間。

但是，如果你的業務場景需要根據用戶ID或商品ID等欄位進行頻繁的查詢和排序，那麼就應該考慮將這些欄位作為主鍵。在這種情況下，使用自增主鍵可能會導致數據的插入順序與查詢順序不一致，降低查詢效率。

因此，在設計主鍵時，需要根據具體業務場景進行選擇。

‍