共计 2842 个字符，预计需要花费 8 分钟才能阅读完成。
InnoDB 的一棵 B + 树能够寄存多少行数据？
答案：约 2 千万
为什么是这么多？
因为这是能够算进去的，要搞清楚这个问题，先从 InnoDB 索引数据结构、数据组织形式说起。
计算机在存储数据的时候，有最小存储单元，这就好比现金的流通最小单位是一毛。
在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如 XFS/EXT4）的最小单元是块，一个块的大小是 4k，而对于 InnoDB 存储引擎也有本人的最小贮存单元，页（Page），一个页的大小是 16K。
上面几张图能够了解最小存储单元：
文件系统中一个文件大小只有 1 个字节，但不得不占磁盘上 4KB 的空间。
InnoDB 的所有数据文件（后缀为 ibd 的文件），大小始终都是 16384（16k）的整数倍。
磁盘扇区、文件系统、InnoDB 存储引擎都有各自的最小存储单元。
在 MySQL 中，InnoDB 页的大小默认是 16k，当然也能够通过参数设置：
表中的数据都是存储在页中的，所以一个页中能存储多少行数据呢？
假如一行数据的大小是 1k，那么一个页能够寄存 16 行这样的数据。
如果数据库只按这样的形式存储，如何查找数据就成为一个问题，因为不晓得要查找的数据存在哪个页中，也不可能把所有的页遍历一遍，那样太慢了。
不过，能够应用 B + 树的形式组织这些数据，如图所示：
先将数据记录按主键进行排序，别离寄存在不同的页中（为了便于了解这里一个页中只寄存 3 条记录，理论状况能够寄存很多）
除了存放数据的页以外，还有寄存键值 + 指针的页，如图中 page number= 3 的页，该页寄存键值和指向数据页的指针，这样的页由 N 个键值 + 指针组成。
当然它也是排好序的。这样的数据组织模式，咱们称为索引组织表。
当初来看下，要查找一条数据，怎么查？
如：select * from user where id=5;
这里 id 是主键，通过这棵 B + 树来查找，首先找到根页，你怎么晓得 user 表的根页在哪呢？
其实每张表的根页地位在表空间文件中是固定的，即 page number= 3 的页。
找到根页后通过二分查找法，定位到 id= 5 的数据应该在指针 P5 指向的页中，那么进一步去 page number= 5 的页中查找，同样通过二分查问法即可找到 id= 5 的记录：
| 5 | zhao2 | 27 |
当初分明了 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 + 树能够寄存：1170117016=21902400 条这样的记录。
所以在 InnoDB 中 B + 树高度个别为 1 - 3 层，它就能满足千万级的数据存储。
在查找数据时，一次页的查找代表一次 IO，所以通过主键索引查问通常只须要 1 - 3 次 IO 操作即可查找到数据。
怎么失去 InnoDB 主键索引 B + 树的高度？
下面通过推断得出 B + 树的高度通常是 1 -3，上面从另外一个侧面证实这个论断。
在 InnoDB 的表空间文件中，约定 page number 为 3 的代表主键索引的根页，而在根页偏移量为 64 的中央寄存了该 B + 树的 page level。
如果 page level 为 1，树高为 2，page level 为 2，则树高为 3。即 B + 树的高度 =page level+1；上面将从理论环境中尝试找到这个 page level。
在实际操作之前，能够通过 InnoDB 元数据表确认主键索引根页的 page number 为 3，也能够从《InnoDB 存储引擎》这本书中失去确认。
能够看出数据库 dbt3 下的 customer 表、lineitem 表主键索引根页的 page number 均为 3，而其余的二级索引 page number 为 4。
对于二级索引与主键索引的区别请参考 MySQL 相干书籍，本文不在此介绍。
上面对数据库表空间文件做想相干的解析：
因为主键索引 B + 树的根页在整个表空间文件中的第 3 个页开始，所以能够算出它在文件中的偏移量：16384*3=49152（16384 为页大小）。
另外依据《InnoDB 存储引擎》中形容在根页的 64 偏移量地位前 2 个字节，保留了 page level 的值
因而我想要的 page level 的值在整个文件中的偏移量为：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 表的 page level 为 2，B+ 树高度为 page level+1=3；
这三张表的数据量如下：
总结：
lineitem 表的数据行数为 600 多万，B+ 树高度为 3，customer 表数据行数只有 15 万，B+ 树高度也为 3。能够看出只管数据量差别较大，这两个表树的高度都是 3
换句话说这两个表通过索引查问效率并没有太大差别，因为都只须要做 3 次 IO。那么如果有一张表行数是一千万，那么他的 B + 树高度仍旧是 3，查问效率依然不会相差太大。
region 表只有 5 行数据，当然他的 B + 树高度为 1。
面试题
有一道 MySQL 的面试题，为什么 MySQL 的索引要应用 B + 树而不是其它树形构造? 比方 B 树？
这个问题的简单版本能够参考本文；
简略答复是：
因为 B 树不论叶子节点还是非叶子节点，都会保留数据，这样导致在非叶子节点中能保留的指针数量变少（有些材料也称为扇出）
指针少的状况下要保留大量数据，只能减少树的高度，导致 IO 操作变多，查问性能变低；
小结
本文从一个问题登程，逐渐介绍了 InnoDB 索引组织表的原理、查问形式，并联合已有常识，答复该问题，联合实际来证实。
当然为了表述简略易懂，文中疏忽了一些细枝末节，比方一个页中不可能所有空间都用于存放数据，它还会寄存一些大量的其余字段比方 page level，index number 等等，另外还有页的填充因子也导致一个页不可能全副用于保留数据。
