面试官:MySQL 存储数据过多，为啥会变慢？

面试官:MySQL 存储数据过多，为啥会变慢？

目前大部分数据库系统及文件系统都采用BTree或其变种B+Tree作为索引结构，mysql 快与慢与索引结构有较大关系。

什么是 B 树？

B 树也叫 B- 树。B+树与B树，这两种数据结构既有相似之处，也有他们的区别。

• 所有叶子节点都在同一层级；
• 除了根节点以外的其他节点包含的key值数量在[m/2]-1到m-1的数据范围；
• 除了根节点和叶子节点外，所有中间节点至少有m/2个孩子节点；
• 根节点如果不是叶子节点的话，它必须包含至少2个孩子节点；
• 拥有n-1个key值非叶子节点必须有n个孩子节点；
• 一个节点的所有key值必须是升序排序的；

什么是 B+ 树

• B+树包含2种类型的节点：内部节点（也称索引节点）和叶子节点。根节点本身即可以是内部节点，也可以是叶子节点。根节点的关键字key个数最少可以只有1个；
• B+树与B树最大的不同是内部节点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子节点中；
• m阶B+树表示了内部节点最多有m-1个关键字（或者说内部节点最多有m个子树，和B树相同），阶数m同时限制了叶子节点最多存储m-1个记录；
• 内部节点中的key都按照从小到大的顺序排列，对于内部节点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子节点中的记录也按照key的大小排列；
• 每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依关键字的大小自小而大顺序链接；

再来说说为啥会变慢？

假设创建一个 user 表, 在硬盘上放在了user.ibd文件下。含义是user表的innodb data文件，也叫表空间。

页

一页是 16K 大小，引入页号唯一标识具体是哪一页，页号其实是一个表空间的地址偏移量。同时引入了前后指针，把这些数据页给关联起来，用于指向前后的页。页号和指针被加到了页头里。

页是如何组成索引的？

为了加速搜索，便有了索引的概念。

每个数据页里选出主键id最小的 record，存储它们的主键id和所在页的页号。组成新的record，放入到一个新生成的一个数据页中，这个新数据页跟之前的数据页结构没啥区别，暂且叫它索引页，而且大小还是16k。

索引页跟之前数据页的区别是加入了页层级page level的信息。

从0开始往上算。于是页与页之间就有了上下层级的概念，就像下面这样。

假设一次查询过程中查询了三个页，如果这三个页都在磁盘中（没有被提前加载到内存中），那么最多需要经历三次磁盘IO查询，它们才能被加载到内存中。IO 操作是比较慢的，因此要IO操作越少越好，查询才会快。

B+树能放多少这样的索引页？

B+ 树只叶子结点存放数据（record),非叶子结点 只存放索引(id+页号)

• x - 多少页
• y - 多少行数据
• z - 索引树高

B+到底可以存放多少数据行？

主键假设是bigint（8Byte），而页号在源码里 FIL_PAGE_OFFSET（4Byte），那么非叶子节点里的一条数据是12Byte左右。

一页 16K，假设页头+页尾+页目录 占用了 1K 空间，还剩 15K, 15K/12Byte = 1280 条，也就是可以存 1280 页目录。也即是 x = 1280

假设页头+页尾+页目录 占用了 1K 空间，一条行记录的数据 是 1K, 那么一页能存储 15条数据，

行总数计算 回到 (x ^ (z-1)) * y 这个公式。

• 已知x=1280，y=15。
• 假设B+树是两层，那z=2。则是(1280 ^ (2-1)) * 15 ≈ 2w
• 假设B+树是三层，那z=3。则是(1280 ^ (3-1)) * 15 ≈ 2.5kw

这也是为啥单表 2Kw 数据以内比较好，z=3 至少需要3次磁盘IO，对性能的影响还好，如果要存储更多数据，比如 z=4，(1280 ^ (4-1)) * 15 ≈ 314.6亿 行数据。至少4次IO，磁盘性能会受影响了。

如果换成 B 树呢？

B树会在叶子和非叶子结点上都放数据，结构图下：

此时行数的计算公式，类似等比数列。

假设页头+页尾+页目录 占用了 1K 空间，一条行记录的数据 是 1K, 那么一页能存储 15条数据，

15 + 15^2 +15^3 + ... + 15^z

z>=6 时，才会时 2Kw 数据， z>=6 说明至少要 6次磁盘IO, 磁盘 IO 越多越慢，这也是为啥 mysql 选择 B+ 树作为索引树。

为啥磁盘慢？

与主存不同，磁盘I/O存在机械运动耗费，与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

通过寻址的方式，转动磁盘，寻找数据是很费时间的。影响读写效率。