前言
Hello 我又来了, 快年底了, 作为一个有抱负的码农, 我想给自己攒一个年终总结. 索性这次把数据库中最核心的也是最难搞懂的内容, 也就是索引, 分享给大家.
这篇博客我会谈谈对于索引结构我自己的看法, 以及分享如何从零开始一层一层向上最终理解索引结构, 书接上文.
多页模式
在多页模式下, MySQL 终于可以完成多数据的存储了, 就是采用开辟新页的方式, 将多条数据放在不同的页中, 然后同样采用链表的数据结构, 将每一页连接起来. 那么可以思考第四个问题: 多页情况下是否对查询效率有影响呢?
多页模式对于查询效率的影响
针对这个问题, 既然问出来了, 那么答案是肯定的, 多页会对查询效率产生一定的影响, 影响主要就体现在, 多页其本质也是一个链表结构, 只要是链表结构, 查询效率一定不会高.
假设数据又非常多条, 数据库就会开辟非常多的新页, 而这些新页就会像链表一样连接在一起, 当我们要在这么多页中查询某条数据时, 它还是会从头节点遍历到存在我们要查找的那条数据所存在的页上, 我们好不容易通过页目录优化了页中数据的查询效率, 现在又出现了以页为单位的链表, 这不是前功尽弃了吗?
如何优化多页模式
由于多页模式会影响查询的效率, 那么肯定需要有一种方式来优化多页模式下的查询. 相信有同学已经猜出来了, 既然我们可以用页目录来优化页内的数据区, 那么我们也可以采取类似的方式来优化这种多页的情况.
是的, 页内数据区和多页模式本质上都是链表, 那么的确可以采用相同的方式来对其进行优化, 它就是目录页.
所以我们对比页内数据区, 来分析如何优化多页结构. 在单页时, 我们采用了页目录的目录项来指向一行数据, 这条数据就是存在于这个目录项中的最小数据, 那么就可以通过页目录来查找所需数据.
所以对于多页结构也可以采用这种方式, 使用一个目录项来指向某一页, 而这个目录项存放的就是这一页中存放的最小数据的索引值. 和页目录不同的地方在于, 这种目录管理的级别是页, 而页目录管理的级别是行.
那么分析到这里, 我们多页模式的结构就会是下图所示的这样:
存在一个目录页来管理页目录, 目录页中的数据存放的就是指向的那一页中最小的数据.
这里要注意的一点是: 其实目录页的本质也是页, 普通页中存的数据是项目数据, 而目录页中存的数据是普通页的地址.
假设我们要查找 id=19 的数据, 那么按照以前的查找方式, 我们需要从第一页开始查找, 发现不存在那么再到第二页查找, 一直找到第四页才能找到 id=19 的数据, 但是如果有了目录页, 就可以使用 id=19 与目录页中存放的数据进行比较, 发现 19 大于任何一条数据, 于是进入 id=16 指向的页进行查找, 直接然后再通过页内的页目录行级别的数据的查找, 很快就可以找到 id 为 19 的数据了. 随着数据越来越多, 这种结构的效率相对于普通的多页模式, 优势也就越来越明显.
回归正题, 相信有对 MySQL 比较了解的同学已经发现了, 我们画的最终的这幅图, 就是 MySQL 中的一种索引结构 --B + 树.
B + 树的引入
我们将我们画的存在目录页的多页模式图宏观化, 可以形成下面的这张图:
这就是我们兜兜转转由简到繁形成的一颗 B + 树. 和常规 B + 树有些许不同, 这是一棵 MySQL 意义上的 B + 树, MySQL 的一种索引结构, 其中的每个节点就可以理解为是一个页, 而叶子节点也就是数据页, 除了叶子节点以外的节点就是目录页.
这一点在图中也可以看出来, 非叶子节点只存放了索引, 而只有叶子节点中存放了真实的数据, 这也是符合 B + 树的特点的.
B + 树的优势
由于叶子节点上存放了所有的数据, 并且有指针相连, 每个叶子节点在逻辑上是相连的, 所以对于范围查找比较友好.
B + 树的所有数据都在叶子节点上, 所以 B + 树的查询效率稳定, 一般都是查询 3 次.
B + 树有利于数据库的扫描.
B + 树有利于磁盘的 IO, 因为他的层高基本不会因为数据扩大而增高(三层树结构大概可以存放两千万数据量.
页的完整结构
说完了页的概念和页是如何一步一步地组合称为 B + 树的结构之后, 相信大家对于页都有了一个比较清楚的认知, 所以这里就要开始说说官方概念了, 基于我们上文所说的, 给出一个完整的页结构, 也算是对上文中自己理解页结构的一种补充.
上图为 Page 数据结构, File Header 字段用于记录 Page 的头信息, 其中比较重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段, 通过这两个字段, 我们可以找到该页的上一页和下一页, 实际上所有页通过两个字段可以形成一条双向链表.
Page Header 字段用于记录 Page 的状态信息. 接下来的 Infimum 和 Supremum 是两个伪行记录, Infimum(下确界)记录比该页中任何主键值都要小的值, Supremum (上确界)记录比该页中任何主键值都要大的值, 这个伪记录分别构成了页中记录的边界.
User Records 中存放的是实际的数据行记录, 具体的行记录结构将在本文的第二节中详细介绍. Free Space 中存放的是空闲空间, 被删除的行记录会被记录成空闲空间. Page Directory 记录着与二叉查找相关的信息. File Trailer 存储用于检测数据完整性的校验和等数据.
来源: https://www.cnblogs.com/zydj333/p/12031716.html