先创建一張商品表，id 為主鍵（如果沒有指定主鍵，預設選擇第一個不包含 NULL 值的唯一列作為聚簇索引的索引鍵（key））：
CREATE TABLE `product` (
`id` int NOT NULL,
`product_no` varchar(20) DEFAULT NULL,
`name` varchar(255) DEFAULT NULL,
`price` decimal(10,2) DEFAULT NULL,
PRIMARY KEY (`id`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci ROW_FORMAT=DYNAMIC;
INSERT INTO product (id, product_no, name, price) VALUES
(1, 'P001', '商品1', 10.00),
(2, 'P002', '商品2', 20.00),
(3, 'P003', '商品3', 30.00),
(4, 'P004', '商品4', 40.00),
(5, 'P005', '商品5', 50.00),
(6, 'P006', '商品6', 60.00),
(7, 'P007', '商品7', 70.00),
(8, 'P008', '商品8', 80.00),
(9, 'P009', '商品9', 90.00),
(10, 'P010', '商品10', 100.00);
行數據：
以上插入的行數據，存儲在 B+Tree 索引時的樣子如下：
B+Tree 是一種多叉樹，葉子節點才存放數據，非葉子節點只存放索引，而且每個節點裡的數據是按主鍵順序存放的。每一層父節點的索引值都會出現在下層子節點的索引值中，因此在葉子節點中，包括了所有的索引值信息，並且每一個葉子節點都有兩個指針，分別指向下一個葉子節點和上一個葉子節點，形成一個雙向鏈表（下圖葉子節點圖片中是單向鏈表，實際為雙向，圖片有誤）。
主鍵索引的 B+Tree
通過主鍵查詢商品數據的過程#
比如，執行了以下查詢語句：
select * from product where id= 5;
這條語句使用了主鍵索引查詢 id 號為 5 的商品。查詢過程是這樣的，B+Tree 會自頂向下逐層進行查找：
- 將 5 與根節點的索引數據 (1，10，20) 比較，5 在 1 和 10 之間，所以根據 B+Tree 的搜索邏輯，找到第二層的索引數據 (1，4，7)；
- 在第二層的索引數據 (1，4，7) 中進行查找，因為 5 在 4 和 7 之間，所以找到第三層的索引數據（4，5，6）；
- 在葉子節點的索引數據（4，5，6）中進行查找，然後我們找到了索引值為 5 的行數據。
數據庫的索引和數據都是存儲在硬碟的，我們可以把讀取一個節點當作一次磁碟 I/O 操作。那麼上面的整個查詢過程一共經歷了 3 個節點，也就是進行了 3 次 I/O 操作。
B+Tree 存儲千萬級的數據只需要 3-4 層高度就可以滿足，這意味著從千萬級的表查詢目標數據最多需要 3-4 次磁碟 I/O，所以B+Tree 相比於 B 樹和二叉樹來說，最大的優勢在於查詢效率很高，因為即使在數據量很大的情況，查詢一個數據的磁碟 I/O 依然維持在 3-4 次。
通過二級索引查詢商品數據的過程#
主鍵索引的 B+Tree 和二級索引的 B+Tree 區別如下：
- 主鍵索引的 B+Tree 的葉子節點存放的是實際數據，所有完整的數據記錄都存放在主鍵索引的 B+Tree 的葉子節點裡
- 二級索引的 B+Tree 的葉子節點存放的是主鍵值，而不是實際數據
將 product 表中的 product_no（商品編碼）字段設置為二級索引：
CREATE UNIQUE INDEX product_product_no_IDX USING BTREE ON test.product (product_no);
它的 B+Tree 如下 (下圖葉子節點圖片中是單向鏈表，實際為雙向，圖片有誤）：
其中非葉子的 key 值是 product_no（圖中橙色部分），葉子節點存儲的數據是主鍵值（圖中綠色部分）。
用 product_no 二級索引查詢商品，如下：
select * from product where product_no = '0002';
會先檢二級索引中的 B+Tree 的索引值（商品編碼，product_no），找到對應的葉子節點，然後獲取主鍵值，然後再通過主鍵索引中的 B+Tree 樹查詢到對應的葉子節點，然後獲取整行數據。這個過程叫「回表」，也就是說要查兩個 B+Tree 才能查到數據。如下圖（下圖葉子節點圖片中是單向鏈表，實際為雙向，圖片有誤）：
不過，當查詢的數據（僅查詢主鍵）能在二級索引的 B+Tree 的葉子節點裡查詢到，這時就不用再查主鍵索引查，比如下面這條查詢語句：
select id from product where product_no = '0002';
這種在二級索引的 B+Tree 就能查詢到結果的過程就叫作「覆蓋索引」，也就是只需要查一個 B+Tree 就能找到數據。****
為什麼 MySQL InnoDB 選擇 B+tree 作為索引的資料結構？
1. B+Tree vs B Tree#
B+Tree 只在葉子節點存儲數據，而 B 樹 的非葉子節點也要存儲數據，所以 B+Tree 的單個節點的數據量更小，在相同的磁碟 I/O 次數下，就能查詢更多的節點。
另外，B+Tree 葉子節點採用的是雙向鏈表連接，適合 MySQL 中常見的基於範圍的順序查找，而 B 樹無法做到這一點。
2. B+Tree vs 二叉樹#
對於有 N 個葉子節點的 B+Tree，其搜索複雜度為O(logdN)，其中 d 表示節點允許的最大子節點個數為 d 個。
在實際的應用當中， d 值是大於 100 的，這樣就保證了，即使數據達到千萬級別時，B+Tree 的高度依然維持在 3~4 層左右，也就是說一次數據查詢操作只需要做 3~4 次的磁碟 I/O 操作就能查詢到目標數據。
而二叉樹的每個父節點的子節點個數只能是 2 個，意味著其搜索複雜度為 O(logN)，這已經比 B+Tree 高出不少，因此二叉樹檢索到目標數據所經歷的磁碟 I/O 次數要更多。
3. B+Tree vs Hash#
Hash 在做等值查詢的時候效率很快，搜索複雜度為 O (1)。
但是 Hash 表不適合做範圍查詢，它更適合做等值的查詢，這也是 B+Tree 索引要比 Hash 表索引有著更廣泛的適用場景的原因。****