java八股文面试[数据库]——一个B+树中大概能存放多少条索引记录

MySQL设计者将一个B+Tree的节点的大小设置为等于一个页. (这样做的目的是每个节点只需要一次I/O就可以完全载入), InnoDB的一个页的大小是16KB,所以每个节点的大小也是16KB, 并且B+Tree的根节点是保存在内存中的,子节点才是存储在磁盘上.

假设一个B+树高为2，即存在一个根节点和若干个叶子节点，那么这棵B+树的存放总记录数为：

根节点指针数*单个叶子节点记录行数.

• 计算根节点指针数: 假设表的主键为INT类型,占用的就是4个字节,或者是BIGINT占用8个字节, 指针大小为6个字节,那么一个页(就是B+Tree中的一个节点) ,大概可以存储: 16384B / (4B+6B) = 1638 ,一个节点最多可以存储1638个索引指针.

• 计算每个叶子节点的记录数:我们假设一行记录的数据大小为1k,那么一页就可以存储16行数据,16KB / 1KB = 16.

• 一颗高度为2的B+Tree可以存放的记录数为: 1638 * 16=26208 条数据记录, 同样的原理可以推算出一个高度3的B+Tree可以存放: 1638 * 1638 * 16 = 42928704条这样的记录.

所以InnoDB中的B+Tree高度一般为1-3层,就可以满足千万级别的数据存储,在查找数据时一次页的查找代表一次 IO，所以通过主键索引查询通常只需要 1-3 次 IO 操作即可查找到数据。

知识来源：马士兵教育