MySQL B+Tree 索引的存储和查询

先创建一张商品表，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 表索引有着更广泛的适用场景的原因。****

myEsn2E9