# MySQL索引为什么要用B+树实现？

在这里插入图片描述

# 为什么不用二叉树或者红黑树

在大规模数据存储中，树的高度决定了查询的磁盘I/O次数

二叉树/红黑树：每个节点最多只有2个子节点。如果数据有数百万条，树的高度可能会达到几十层甚至更高。

B+树：它是“多路平衡查找树”，每个节点可以拥有数百甚至上千个子节点（分支因子非常大）。这样可以将树的高度压缩得极低，通常只有3到4层。这意味着，哪怕在千万级的数据量下，查一条数据最多也只需要3到4次磁盘I/O

多路平衡查找树（Multi-way Balanced Search Tree）是计算机科学中一种非常经典的数据结构，我们可以把它拆开来理解：

多路（Multi-way）：普通的二叉树每个节点最多只能有两个“分叉”（左和右）。而“多路”意味着一个节点可以有多个子节点（比如 3 个、4 个甚至成百上千个）。

平衡（Balanced）：树的左边和右边高度几乎一样，没有“偏科”。这样能保证不管你找哪个数据，花的时间都差不多，不会出现最坏的情况。

查找树（Search Tree）：树里的数据是有序排列的，左边小、右边大，专门为了快速买、查数据而设计。

简单来说，它就是二叉查找树（BST）的升级加强版。

B树：每个节点不仅存“索引键”（Key），还存“整行数据”（Value）。这就导致每个节点占用的空间很大，一页磁盘（默认16KB）能存的索引数量变少，树会变高。

B+树：非叶子节点只存索引键，不存任何数据行；所有的数据都放在最底层的叶子节点。因为非叶子节点变轻量了，一个16KB的节点能容纳更多的索引，进一步降低了树的高度。

B树：进行范围查询（比如 WHERE age BETWEEN 18 AND 30）时，需要不停地在子节点和父节点之间“来回倒腾”（中序遍历），极其低效。

B+树：所有叶子节点之间用一个双向链表串联了起来。当找到18岁的第一个节点后，只需要顺着链表往后查数据，直到看见30岁为止，完全不需要再去翻上面的父节点。这让范围查询和排序变得极快。

在这里插入图片描述

计算的核心思想是：一层能容纳多少个指针（分支因子）。

假设一条数据行的大小为 RowSize，我们先定义4个基本指标：

InnoDB页大小（Page Size）：默认是 16 KB（即 $16384$ 字节）。
页头与预留空间：每一页并不是16KB全能用来存数据，扣除页头（File Header、Page Header等）以及预留的空闲空间，实际可用空间大约为 15 KB（约 $15360$ 字节）。
主键键值大小（Key Size）：如果是 INT 占 4 字节；如果是 BIGINT 占 8 字节。
指针大小（Pointer Size）：在InnoDB中，非叶子节点的指针通常占 6 字节。

步骤 1：计算非叶子节点（索引页）能容纳的分支数 $N$

非叶子节点的一个“索引项”由主键键值 + 子节点指针组成。

假设主键是 BIGINT（8字节），指针是6字节，那么一个索引项大小 = $8 + 6 = 14$ 字节。
一个16KB的索引页能容纳的项目数 $N = 15360 \text{ 字节} \div 14 \text{ 字节} \approx 1097$ 个。结论：在B+树的非叶子节点中，一个节点大约可以指向 1100 个子节点。

步骤 2：计算叶子节点（数据页）能容纳的数据行数 $M$

叶子节点存放的是真正的整行数据。假设通过你的评估，你表里的一行数据（包含所有字段）大小为 RowSize（例如 1 KB，即 1024 字节）。一个16KB的数据页能容纳的行数 $M = 15360 \text{ 字节} \div 1024 \text{ 字节} = 15$ 行。

有了 $N$ （分支数）和 $M$ （单页行数），我们就可以根据总数据量来算高度了。

如果树的高度 $H = 2$ （1层索引 + 1层数据）根节点（非叶子节点）可以指向 $N$ 个叶子节点。每个叶子节点存 $M$ 条数据。总容量 = $N \times M$ 举例： $1100 \times 15 = 16,500$ 条数据。
如果树的高度 $H = 3$ （2层索引 + 1层数据）根节点指向 $N$ 个第二层索引节点。第二层索引节点总共可以指向 $N \times N$ 个叶子节点。总容量 = $N^2 \times M$ 举例： $1100^2 \times 15 = 1,210,000 \times 15 \approx 18,150,000$ 条数据（约1800万条）。
如果树的高度 $H = 4$ （3层索引 + 1层数据）总容量 = $N^3 \times M$ 举例： $1100^3 \times 15 \approx 199$ 亿条数据。