但是在一开始生成页的时候，其实并没有 User Records 这个部分，每当我们插入一条记录，都会从 Free Space 部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到 User Records 部分，当 Free Space 部分的空间全部被 User Records 部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了。这个过程的图示如下。
刚刚上面说到了数据的新增的过程。
那下面就来说说，数据的查找过程，假如我们需要查找一条记录，我们可以把表空间中的每一页都加载到内存中，然后对记录挨个判断是不是我们想要的，在数据量小的时候，没啥问题，内存也可以撑；但是现实就是这么残酷，不会给你这个局面；为了解决这问题，mysql 中就有了索引的概念；大家都知道索引能够加快数据的查询，那到底是怎么个回事呢？下面我就来看看。
6 索引的数据结构
在 mysql 中索引的数据结构和刚刚描述的页几乎是一模一样的，而且大小也是 16K, 但是在索引页中记录的是页 (数据页，索引页) 的最小主键 id 和页号，以及在索引页中增加了层级的信息，从 0 开始往上算，所以页与页之间就有了上下层级的概念。
看到这个图之后，是不是有点似曾相似的感觉，是不是像一棵二叉树啊，对，没错！它就是一棵树，只不过我们在这里只是简单画了三个节点，2 层结构的而已，如果数据多了，可能就会扩展到 3 层的树，这个就是我们常说的 B+ 树，最下面那一层的 page level =0, 也就是叶子节点，其余都是非叶子节点。
5, 那按照二分法查找的规则，肯定就往右侧节点继续查找，找到页号 30 的节点后，发现这个节点还有子节点（非叶子节点），那就继续比对，同理，6>5&&6看上图中，我们是单拿一个节点来看，首先它是一个非叶子节点（索引页），在它的内容区中有 id 和 页号地址两部分，这个 id 是对应页中记录的最小记录 id 值，页号地址是指向对应页的指针；而数据页与此几乎大同小异，区别在于数据页记录的是真实的行数据而不是页地址，而且 id 的也是顺序的。
5, 那按照二分法查找的规则，肯定就往右侧节点继续查找，找到页号 30 的节点后，发现这个节点还有子节点（非叶子节点），那就继续比对，同理，6>5&&67 单表建议值
5, 那按照二分法查找的规则，肯定就往右侧节点继续查找，找到页号 30 的节点后，发现这个节点还有子节点（非叶子节点），那就继续比对，同理，6>5&&6下面我们就以 3 层，2 分叉（实际中是 M 分叉）的图例来说明一下查找一个行数据的过程。
5, 那按照二分法查找的规则，肯定就往右侧节点继续查找，找到页号 30 的节点后，发现这个节点还有子节点（非叶子节点），那就继续比对，同理，6>5&&6比如说我们需要查找一个 id=6 的行数据，因为在非叶子节点中存放的是页号和该页最小的 id，所以我们从顶层开始对比，首先看页号 10 中的目录，有 [id=1, 页号 = 20],[id=5, 页号 = 30], 说明左侧节点最小 id 为 1，右侧节点最小 id 是 5；6>5, 那按照二分法查找的规则，肯定就往右侧节点继续查找，找到页号 30 的节点后，发现这个节点还有子节点（非叶子节点），那就继续比对，同理，6>5&&6
5, 那按照二分法查找的规则，肯定就往右侧节点继续查找，找到页号 30 的节点后，发现这个节点还有子节点（非叶子节点），那就继续比对，同理，6>5&&6从上述的过程中发现，我们为了查找 id=6 的数据，总共查询了三个页，如果三个页都在磁盘中（未提前加载至内存），那么最多需要经历三次的磁盘 IO。需要注意的是，图中的页号只是个示例sql取最大的一条数据，实际情况下并不是连续的，在磁盘中存储也不一定是顺序的。
至此，我们大概已经了解了表的数据是怎么个结构了，也大概知道查询数据是个怎么的过程了，这样我们也就能大概估算这样的结构能存放多少数据了。
从上面的图解我们知道 B+ 数的叶子节点才是存在数据的，而非叶子节点是用来存放索引数据的。
所以，同样一个 16K 的页sql取最大的一条数据，非叶子节点里的每条数据都指向新的页，而新的页有两种可能
假设
如下图中所示Total =x^(z-1) *y 也就是说总数会等于 x 的 z-1 次方 与 Y 的乘积。
X =？
在文章的开头已经介绍了页的结构，索引也也不例外，都会有 File Header (38 byte)、Page Header (56 Byte)、Infimum + Supermum（26 byte）、File Trailer（8byte）, 再加上页目录，大概 1k 左右，我们就当做它就是 1K, 那整个页的大小是 16K, 剩下 15k 用于存数据，在索引页中主要记录的是主键与页号，主键我们假设是 Bigint (8 byte), 而页号也是固定的（4Byte）, 那么索引页中的一条数据也就是 12byte; 所以 x=15*1024/12≈1280 行。
Y=？
叶子节点和非叶子节点的结构是一样的，同理，能放数据的空间也是 15k；但是叶子节点中存放的是真正的行数据，这个影响的因素就会多很多，比如，字段的类型，字段的数量；每行数据占用空间越大，页中所放的行数量就会越少；这边我们暂时按一条行数据 1k 来算，那一页就能存下 15 条，Y≈15。
算到这边了，是不是心里已经有谱了啊根据上述的公式，Total =x^(z-1) y，已知 x=1280,y=15假设 B+ 树是两层，那就是 Z =2， Total = （1280 ^1 ）15 = 19200假设 B+ 树是三层，那就是 Z =3， Total = （1280 ^2） *15 = 24576000 （约 2.45kw）
哎呀，妈呀！这不是正好就是文章开头说的最大行数建议值 2000w 嘛！对的，一般 B+ 数的层级最多也就是 3 层，你试想一下，如果是 4 层，除了查询的时候磁盘 IO 次数会增加，而且这个 Total 值会是多少，大概应该是 3 百多亿吧，也不太合理，所以，3 层应该是比较合理的一个值。
到这里难道就完了？
不我们刚刚在说 Y 的值时候假设的是 1K ，那比如我实际当行的数据占用空间不是 1K , 而是 5K, 那么单个数据页最多只能放下 3 条数据同样，还是按照 Z=3 的值来计算，那 Total = （1280 ^2） *3 = 4915200 （近 500w）
所以，在保持相同的层级（相似查询性能）的情况下，在行数据大小不同的情况下，其实这个最大建议值也是不同的，而且影响查询性能的还有很多其他因素，比如，数据库版本，服务器配置，sql 的编写等等，MySQL 为了提高性能，会将表的索引装载到内存中。在 InnoDB buffer size 足够的情况下，其能完成全加载进内存，查询不会有问题。但是，当单表数据库到达某个量级的上限时，导致内存无法存储其索引，使得之后的 SQL 查询会产生磁盘 IO，从而导致性能下降，所以增加硬件配置（比如把内存当磁盘使），可能会带来立竿见影的性能提升哈。
8 总结
参考资料：
– EOF –
———END———
限 时 特 惠：本站每日持续更新海量各大内部创业教程，一年会员只需128元，全站资源免费下载点击查看详情
站 长 微 信：jiumai99
×