一道面试题：InnoDB中B+树能存储多少行数据？这个问题的简单答案是：大约2000万。图片来自Pexels。为什么有这么多？因为可以计算。为了弄清楚这个问题，我们先从InnoDB的索引数据结构和数据组织方式说起。我们都知道，计算机在存储数据时，有最小的存储单位，就像我们今天流通的现金的最小单位是一角硬币。计算机中磁盘存储数据的最小单位是扇区，一个扇区的大小为512字节，而文件系统（如XFS/EXT4）的最小单位是块，一个块的大小为4K。而对于我们的InnoDB存储引擎，它也有自己的最小存储单元——页（Page），一个页的大小为16K。以下图片可以帮助您了解最小存储单元。文件系统中一个文件的大小只有1个字节，但它却要占用4KB的磁盘空间。InnoDB的所有数据文件（后缀为ibd的文件）总是16384（16K）的整数倍。磁盘扇区、文件系统和InnoDB存储引擎都有自己的最小存储单元。在MySQL中，我们InnoDB页面的大小默认是16K，当然也可以通过参数设置：mysql>showvariableslike'innodb_page_size';+------------------+-------+|Variable_name|Value|+----------------+------+|innodb_page_size|16384|+------------------+--------+1rowinset(0.00sec)数据表中的数据存储在页中，那么多少行数据可以存储在一个页面中吗？假设一行数据的大小为1K，那么一个page可以存放16行这样的数据。如果数据库只是这样存储，那么如何查找数据就成了一个问题。因为我们不知道我们要找的数据存在于哪个页面，也不可能遍历所有的页面，太慢了。于是人们想到了一种方法，将这些数据以B+树的形式组织起来，如下图所示：在此处的一页中存储3条记录）。记录，实际情况可以存很多）。除了存储数据的页面，还有存储键值+指针的页面，比如图中页码=3的页面，里面存放的是键值和指向数据页的指针。这样的页面由N个键值+指针组成。当然也是排序的。这种数据组织形式称为索引组织表。现在我们来看看如何找到一条数据？例如：select*fromuserwhereid=5;这里id是主键，我们遍历这个B+树，先找到根页，怎么知道user表的根页在哪里呢？什么？实际上，每个表的根页的位置在表空间文件中是固定的，即页码=3的页（下面我们将进一步证明这一点）。找到根页后，使用二分查找的方式，在指针P5所指向的页面中定位到id=5的数据，然后在pagenumber=5的页面中进一步查找，同样使用二分查找的方式查找id=5的记录：5zhao227知道了InnoDB中主键索引B+树是如何组织查询数据的，我们总结一下：InnoDB存储引擎的最小存储单位是页，可以用来存储数据或键值+指针，在B+树中，叶子节点存放数据，非叶子节点存放键值+指针。索引组织表通过非叶子节点和指针的二分查找方式确定数据在哪个页，然后在数据页中找到需要的数据。那么回到我们最初的问题，B+树通常可以存储多少行数据？这里我们先假设B+树的高度为2，即有一个根节点和若干个叶节点，那么这棵B+树中存储的记录总数为：根节点指针数*数量记录在单个叶节点中的行数。上面我们已经说明了单个叶子节点（页）的记录数=16K/1K=16。（这里假设一行记录的数据大小为1K，其实很多互联网业务的大小数据记录通常为1K左右）。那么现在我们需要计算非叶子节点可以存放多少个指针呢？其实这也很容易计算。我们假设主键ID为bigint类型，长度为8字节，InnoDB源码中设置指针大小为6字节。这样，一共14个字节。我们在一个页面中可以存储多少个这样的单元，实际上代表了有多少个指针，即16384/14=1170。那么可以算出一棵高度为2的B+树，可以存储1170*16=18720条这样的数据记录。根据同样的原理，我们可以计算出一棵高度为3的B+树可以存储：1170*1170*16=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 存储引擎》：SELECTb.name,a.name,index_id,type,a.space,a.PAGE_NOFROMinformation_schema.INNODB_SYS_INDEXESa,information_schema.INNODB_SYS_TABLESbWHEREa.table_id=b.table_idANDa.space<>0;执行结果：可以看出数据库dbt3下customer表和lineitem表的主键索引的根页页码为3，另一个二级索引页码为4。对于二级索引和主键索引请参考MySQL相关书籍，这里不做介绍。接下来我们分析数据库表空间文件：因为主键索引B+树的根页在整个表空间文件中是从第三页开始的，所以可以计算出它在文件中的偏移量：16384*3=49152（16384是页尺寸）。另外，根据《InnoDB 存储引擎》中的描述，pagelevel的值保存在rootpage的64偏移位置的前2个字节。因此，我们想要的页级值在整个文件中的偏移量为：16384*3+64=49152+64=49216，在前2个字节。接下来，我们使用hexdump工具查看表空间文件指定偏移处的数据：linetem表的pagelevel为2，B+树的高度为pagelevel+1=3。region表的pagelevel为0，B+树的高度为pagelevel+1=1。客户表的页级为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树不管是叶子节点还是非叶子节点都会存储数据，这会导致非叶子节点可以存储的指针变少（有些信息也叫fan-out）。在指针少的情况下保存大量的数据，只能增加树的高度，导致更多的IO操作，降低查询性能。本文从一个问题出发，逐步介绍InnoDB索引组织表的原理和查询方法，并结合已有知识进行答题，并结合实践加以证明。当然，为了使介绍简单易懂，文中忽略了一些细节。比如，一个page中的所有空间是不可能存储数据的，它还会存储少量的其他字段，比如pagelevel，indexnumber等等。此外，页面的填充因子也导致页面无法用于存储数据。二级索引的数据访问方法可以参考MySQL相关书籍。他的主要观点是结合主键索引进行回表查询。作者：李平简介：目前在一家O2O互联网公司从事设计开发工作。业余时间，他喜欢跑步、看书、玩游戏。喜欢简单高效的工作环境，熟悉JavaEE、SOA、数据库架构、优化、系统运维，有大型门户、金融系统搭建经验。RHCE，MySQLOCP。MyCAT开源项目的成员。
