【MYSQL】一颗B+树可以保存多少条数据

引言

事万物都有自己的单元体系，若干个小单体组成一个个大的个体。就像拼乐高一样，可以自由组合。所以说，如果能熟悉最小单元，就意味着我们抓住了事物的本事，再复杂的问题也会迎刃而解。

存储单元

存储器范围比较大，但是数据具体怎么存储，有自己的最小存储单元。

1、数据持久化存储磁盘里，磁盘的最小单元是扇区，一个扇区的大小是 512个字节

2、文件系统的最小单元是块，一个块的大小是 4K

3、InnoDB存储引擎，有自己的最小单元，称之为页，一个页的大小是16K

扇区、块、页这三者的存储关系？

mysql数据库中，table表中的记录都是存储在页中，那么一页可以存多少行数据？假如一行数据的大小约为1K字节，那么按 16K / 1K = 16，可以计算出一页大约能存放16条数据。

mysql 的最小存储单元叫做“页”，这么多的页是如何构建一个庞大的数据组织，我们又如何知道数据存储在哪一个页中？

如果逐条遍历，性能肯定很差。为了提升查找速度，我们引入了B+树，先来看下B+树的存储结构

页除了可以存放数据（叶子节点），还可以存放健值和指针（非叶子节点），当然他们是有序的。这样的数据组织形式，我们称为索引组织表。

如：上图中 page number=3的页，该页存放键值和指向数据页的指针，这样的页由N个键值+指针组成

B+ 树是如何检索记录？

首先找到根页，你怎么知道一张表的根页在哪呢？
其实每张表的根页位置在表空间文件中是固定的，即page number=3的页
找到根页后通过二分查找法，定位到id=5的数据应该在指针P5指向的页中
然后再去page number=5的页中查找，同样通过二分查询法即可找到id=5的记录

查询数据库时，不论读一行，还是读多行，都是将这些行所在的整页数据加载，然后在内存中匹配过滤出最终结果。

表的检索速度跟树的深度有直接关系，毕竟一次页加载就是一次IO，而磁盘IO又是比较费时间。对于一张千万级条数B+树高度为3的表与几十万级B+树高度也为3的表，其实查询效率相差不大。

一棵树可以存放多少行数据？

假设B+树的深度为2

这棵B+树的存储总记录数 = 根节点指针数 * 单个叶子节点记录条数

那么指针数如何计算？

假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节。

那么一个页中能存放多少这样的组合，就代表有多少指针，即 16384 / 14 = 1170。那么可以算出一棵高度为2 的B+树，能存放 1170 * 16 = 18720 条这样的数据记录。

同理：高度为3的B+树可以存放的行数 = 1170 * 1170 * 16 = 21902400

千万级的数据存储只需要约3层B+树，查询数据时，每加载一页（page）代表一次IO。所以说，根据主键id索引查询约3次IO便可以找到目标结果。