在MySQL中，当数据量达到千万级时，B+树通常有3层。本文学习如何计算InnoDB中一棵B+树可以存放的数据数，以及如何根据数据量推算出对应的层数。

节点存储结构

在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是512字节，而文件系统（例如XFS/EXT4）他的最小单元是块，一个块的大小是4k，而对于我们的InnoDB存储引擎也有自己的最小储存单元——页（Page），一个页的大小是16K。

InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针，在B+树中叶子节点存放数据，非叶子节点存放键值+指针。

索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而在去数据页中查找到需要的数据。

容量计算

• 叶子节点：假设一行记录的数据大小为1k，InnoDB存储引擎的页大小默认为16k，那么一个叶子节点（即一个页）可以存储16条记录。
• 非叶子节点：假设主键ID为bigint类型，长度为8字节，指针大小在InnoDB源码中为6字节，这样一共14字节，一个页中能存放多少这样的单元，就代表有多少指针，即 16384/（8+6）=1170个指针。

层数计算

B+树的树高为1时，意味着所有数据都存储在根节点（同时也是叶子节点）上。此时，数据量的大小取决于根节点的容量，即根节点可以存储多少条记录。
当B+树高为2甚至更高时，存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：根节点指针数*单个叶子节点记录行数。

• 一层B+树：InnoDB存储引擎的页大小默认为16KB，假设每条记录的大小为1KB，那么根节点可以存储16条记录。
• 两层B+树：根节点为非叶子节点，有1170个指针，每个指针指向一个叶子节点，每个叶子节点有16条记录，所以总共可以存放1170×16=18720条记录。
• 三层B+树：根节点为非叶子节点，有1170个指针，每个指针指向一个非叶子节点，这些非叶子节点又各有1170个指针指向叶子节点，每个叶子节点有16条记录，所以总共可以存放1170×1170×16=21902400条记录。

高扇出特性

B+树的节点扇出非常高，即每个节点包含的子节点数多。这使得B+树能够在较少的层数内存储大量数据，从而在千万级数据量时，通常只需要3层就能满足需求。

磁盘IO优化

B+树通过减少树的高度，降低了磁盘IO次数。在查找数据时，一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。这种设计使得B+树在处理千万级数据量时，仍能保持较高的查询效率。