InnoDB中一棵B+树可以存储多少行数据？ 这个问题的简单答案是：大约2000万。 为什么有这么多？ 因为这个是可以计算的，要搞清楚这个问题，我们先从InnoDB的索引数据结构和数据组织方式说起。
我们都知道，计算机在存储数据时，有最小的存储单位，就像我们今天流通的现金的最小单位是一角硬币。 计算机中磁盘存储数据的最小单位是扇区，一个扇区的大小为512字节，而文件系统（如XFS/EXT4）的最小单位是块，一个块的大小为4k，而对于我们的 InnoDB 存储引擎也有自己的最小存储单元——页（Page），一个页的大小为16K。
以下图片可以帮助您了解最小存储单元：
文件系统中一个文件的大小只有1个字节mysql一张表能存多少条数据，但它却要占用4KB的磁盘空间。
innodb的所有数据文件（后缀为ibd的文件）总是16384（16k）的整数倍。
磁盘扇区、文件系统和 InnoDB 存储引擎都有自己的最小存储单元。
在MySQL中，我们InnoDB页面的大小默认是16k，当然也可以通过参数来设置：
mysql> show variables like 'innodb_page_size';
+------------------+-------+
| Variable_name | Value |
+------------------+-------+
| innodb_page_size | 16384 |
+------------------+-------+
1 row in set (0.00 sec)
数据表中的数据存储在页中，那么一个页中可以存储多少行数据呢？ 假设一行数据的大小是1k，那么一个page可以存放16行这样的数据。
如果数据库只是这样存储的话，怎么找数据就成了问题，因为我们不知道我们要找的数据存在于哪个页面，也不可能遍历所有的页面，太慢了. 于是人们想到了一种方法，用B+树的形式来组织这些数据。 如图所示：
我们先把数据记录按照主键排序，分页存储（这里为了便于理解，一页只存3条记录，实际情况可以存很多条），除此之外的页存储数据，也有存储键值+指针的页，比如图中页码=3的页，存储键值和指向数据页的指针。 这样一个页面由N个键值+指针组成。 当然也是排序的。 这种数据组织形式称为索引组织表。 现在我们来看一下，如何找到一条数据呢？
比如select * from user where id=5;
这里id是主键，我们遍历这个B+树，先找到根页，怎么知道user表的根页在哪里呢？ 实际上，每个表的根页的位置在表空间文件中是固定的，即页码=3的页（下面我们会进一步证明这一点），找到根页后，定位到页id=5 通过二分查找法 数据应该在指针P5指向的页中，再往page number=5的页中查找，同样通过二分查找法找到id=5的记录:
知道了InnoDB中主键索引B+树是如何组织和查询数据的，我们总结一下：
InnoDB 存储引擎的最小存储单元是页。 一个页面可以用来存储数据或者一个键值+指针。 B+树中，叶子节点存放数据，非叶子节点存放键值+指针。
索引组织表通过非叶子节点和指针的二分查找方式确定数据在哪个页，然后在数据页中找到需要的数据；
那么回到我们最初的问题，B+树通常可以存储多少行数据？
这里我们先假设B+树的高度为2，即有一个根节点和若干个叶节点，那么这棵B+树存储的记录总数为：根节点指针数*记录在单个叶节点中的行。
上面我们已经说明了单个叶子节点（页）的记录数=16K/1K=16。（这里假设一行记录的数据大小为1K，其实很多互联网业务的大小数据记录通常为1K左右）。
所以现在我们需要计算非叶子节点可以存储多少个指针。 其实这也很容易计算。 我们假设主键ID是一个长度为8字节的bigint类型，InnoDB源码中设置了指针大小为6字节。 这样一共14个字节，我们在一个页面中可以存放多少个这样的单元，其实就代表了有多少个指针，即16384/14=1170。 那么可以算出一棵高度为2的B+树，可以存储1170*16=18720条这样的数据记录。
根据同样的原理，我们可以计算出一棵高度为3的B+树可以存储：1170117016=21902400条这样的记录。 因此在InnoDB中，B+树的高度一般为1-3层，可以满足千万级别的数据存储。 在查找数据时，一次分页查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO操作就可以找到数据。
如何获取InnoDB主键索引B+树的高度？
上面我们推断出B+树的高度通常是1-3，我们将从另一个侧面来证明这个结论。 InnoDB表空间文件中约定页码3代表主键索引的根页，B+树的页级别存放在根页的偏移量64处。 如果页面层级为1，树高为2，页面层级为2，树高为3。即B+树的高度=页面层级+1； 下面我们就试着从实际环境中寻找这个页面层级。
在实际操作之前，可以通过InnoDB元数据表确认主键索引根页的页码为3，也可以从《InnoDB Storage Engine》一书中得到确认。
SELECT
b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES a,
information_schema.INNODB_SYS_TABLES b
WHERE
a.table_id = b.table_id AND a.space 0;
结果：
可以看出数据库dbt3下customer表和lineitem表的主键索引根页页码为3，而其他二级索引的页码为4。对于二级索引和主键索引的区别，请参考MySQL相关书籍，此处不再介绍。
我们来分析一下数据库表空间文件：
因为主键索引B+树的根页是从整个表空间文件的第三页开始的，所以可以计算出它在文件中的偏移量：16384*3=49152（16384是页大小）。
另外，根据《InnoDB Storage Engine》中的描述，页级别的值保存在根页的64偏移位置的前2个字节，所以我们要的页级别的值的偏移量在整个文件是：16384*3+64=49152+64=49216，前2个字节。
接下来我们使用hexdump工具查看表空间文件指定偏移处的数据：
linetem表的page level为2，B+树的高度为page level+1=3；
region表的page level为0，B+树的高度为page level+1=1；
customer表的页级为2，B+树的高度为页级+1=3；
这三张表的数据量如下：
总结：
lineitem表的数据行数超过600万，B+树的高度为3。customer表的数据行数只有15万，B+树的高度也为3。可以看出，尽管数据量相差很大，但是两张表树的高度都是3。换句话说，两张表通过索引的查询效率并没有太大的区别，因为他们只需要做3个IO。 所以如果有一个1000万行的表，那么它的B+树高度还是3，查询效率还是相差不大。
region表只有5行数据，当然它的B+树高度是1。
最后一个面试问题
有一道MySQL面试题，为什么MySQL索引使用B+树而不是其他树结构？ 比如B树？
现在这个问题的复杂版本可以参考这篇文章；
他的简单版本答案是：
因为B-tree不管叶子节点还是非叶子节点都会保存数据，这样就会导致非叶子节点可以保存的指针变少（有的数据也叫fan-out）。 它可以增加树的高度，导致更多的IO操作和更低的查询性能；
概括
本文从一个问题出发mysql一张表能存多少条数据，逐步介绍InnoDB索引组织表的原理和查询方法，并结合已有知识进行答题，并结合实践进行论证。 当然，为了表述简单易懂，文中省略了一些细节。 例如，不可能将一个页面中的所有空间都存储在数据中。 它还会存储少量其他字段如页级、索引号等，也有页数。 填充因子也使得页面不可能被完全用于存储数据。 二级索引的数据访问方法可以参考MySQL相关书籍。 他的主要观点是结合主键索引来查询回表。
admin