登录
首页 >  数据库 >  MySQL

Mysql InnoDB B+树索引目录项记录页管理

来源:脚本之家

时间:2022-12-28 19:13:10 434浏览 收藏

怎么入门数据库编程?需要学习哪些知识点?这是新手们刚接触编程时常见的问题;下面golang学习网就来给大家整理分享一些知识点,希望能够给初学者一些帮助。本篇文章就来介绍《Mysql InnoDB B+树索引目录项记录页管理》,涉及到MySQLInnoDB、B+树、目录索引,有需要的可以收藏一下

Mysql InnoDB B+树索引目录项记录管理

接上一篇内容,InnoDB 的作者想到一种更灵活的方式来管理所有目录项,是什么?

一、目录项记录页

其实这些用户目录项与用户记录很像,只是目录项中的两个列记录的是主键和页号而已,那么就可以复用之前存储用户记录的数据页来存储目录项。

为了区分用户记录和目录项,仍然使用 record_type 这个属性,当值为 1 时,表示目录项记录,再来复习一遍:

  • 0:普通用户记录
  • 1:目录项记录
  • 2:Infimum 记录
  • 3:Supremum 记录

现在把目录项放到一个新页中,就变成了这样:

  • 目录项记录 record_type 值为 1,普通用户记录的 record_type 值是 0
  • 目录项记录只有主键值和页的编号,两个列

如此一来,目录页跟数据页一样,都可以为主键值生成 Page Directory(页目录),从而在根据主键值查找记录时,使用二分法来加快查询速度。

还是以查找主键值为 20 的记录为例,大致就可以分为 2 步走:

  • 先目录项页(页30)通过二分法快速找到对应的目录项记录。因为 12
  • 到页 9中继续根据二分法快速找到主键为 20 的用户记录。

二、当目录项记录页也变多后

一个页大小是16KB,当数据多的时候,一个页用来存放页目录记录一定不够用。解决办法也很简单,就是整更多的页。

基于上图,假设一个目录项记录页最多只能存放 4 条目录项记录(实际可以存很多),现在继续插入一条主键值为 320 的普通用户记录,这时候就需要多分配一个新页。

现在因为存储目录项记录的页是多个,此时再根据主键值查找一条用户记录,大致需要 3 个步骤(继续查找主键值为 20 的记录):

确定存储目录项记录的页。上图中有2个,分别是页 30 和页 32。因为页 30 表示的目录项主键值在 [1, 320),页 32 的主键值则不小于 320,所以主键 20的记录应该在 页30。

通过存储目录项记录的页确定用户记录真正所在的页(见上文第一部分)

在真正存储用户记录的页找到主键 20 的记录(见上文第一部分)

ok,解决了问题,又来了新的问题。当数据非常多,上面的2个目录项记录页也不够,又会有很多,那如何根据主键值快速定位一个存储目录项记录的页?

解决办法:目录项记录页不是多么?我再给这些页建个更高级的目录不就行了?可以想象一个多级目录,大目录里嵌套小目录,小目录里才是实际的数据。

基于上图,又会演变成这样:

  • 生成了一个更高级的目录项记录的页 33
  • 页中分别 2 条记录,代表页 30 和 页 32
  • 如果用户记录的主键值在 [1, 320) 之间,则到页 30中继续查找
  • 如果用户记录的主键值不小于 320,则到页 32 中继续查找

看出套路来了吧?随着表中记录的增加,这个目录的层级就会继续增加。

三、B+ 树

按照上面的套路,其实可以简化这个目录结构图:

其实这就是 B+ 树。

现在无论是存放用户记录的数据页,还是存放目录项记录的数据页,都存放到 B+ 树这种数据结构中。

  • 所有的数据页都成为 B+ 树的节点。
  • 真正存用户记录的数据页都在 B+树最底层的节点上,称为叶子节点或者叶节点。
  • 而存放目录项记录的节点称为非叶子节点或者内节点。
  • B+ 树最上面的节点称为根节点。

那如果说树的层级深了,找起来不也没那么快吗?

在之前的假设中规定了存放用户记录的页最多3条,存放目录项记录的最多4条,而实际上一个页存放的记录数量是非常大的。

现在继续假设,所有存放用户记录 的叶子节点的数据页可以存放 100 条用户记录,所有存放目录项记录的非叶子节点的数据页可以存放 1000 条目录项记录,那么:

  • 如果 B+树只有 1 层,也就是说只有 1 个用于存放用户记录的节点,那么只能存 100 条用户记录。
  • 如果 B+树有 2 层,则最多存放 1000*100= 100000 条用户记录。
  • 如果 B+树有 3 层,则最多存放 1000*1000*100= 100000000 条用户记录。
  • 如果 B+树有 4 层,则最多存放 1000*1000*1000*100= 100000000000 条用户记录。

也就是说,如果有 4 层的话最多存 1000亿 条记录,很显然表里不会有这么多数据。所以在一般情况下,我们用到的 B+树不超过 4 层。

基于此,通过主键值去查询某条记录,最多只需要进行 4 个页面内的查找(3个存储目录项的页,1个存储用户记录的页)。而在每个页面内有存在页目录 Page Directory,所以在页面内也可以通过二分法快速定位记录。

本文参考书籍: 《mysql是怎样运行的》

到这里,我们也就讲完了《Mysql InnoDB B+树索引目录项记录页管理》的内容了。个人认为,基础知识的学习和巩固,是为了更好的将其运用到项目中,欢迎关注golang学习网公众号,带你了解更多关于mysql的知识点!

声明:本文转载于:脚本之家 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表