Mysql InnoDB引擎中页目录和槽的查找过程

目录
  • Mysql InnoDB引擎页目录
    • 一、页目录和槽
    • 二、页目录的规定
    • 三、页目录查找记录的过程
  • 总结

Mysql InnoDB引擎页目录

一、页目录和槽

接上一篇，现在知道记录在页中按照主键大小顺序串成了单链表。

那么我使用主键查询的时候，最顺其自然的办法肯定是从第一条记录，也就是 Infrimum 记录开始，一直向后找，只要存在总会找到。这种在数据量少的时候还好说，一旦数据多了，遍历耗时一定非常长。

于是，作者又想到了一个好办法，灵感来自于书本中的目录。我们翻书的时候想查找一些内容，就会去查看目录，然后直接确定好内容所在的页码。

那么对于 InnoDB 来说，过程如下：

  • 将所有正常的记录划分为几个组，这里包括那 2 条虚拟记录，但是不包含已经被移除到垃圾链表的记录。
  • 每个组内最后一条记录(也就是最大的那条)就是“大哥”，其他记录都是“小弟”，而“大哥”记录的头信息中的 n_owned 属性表示该组内共有几条记录。
  • 将每个组中最后一条记录在页面中的地址偏移量单独提取出来，按顺序存储到靠近页尾部的地方。

这个地方就是页目录 Page Directory。而上述的地址偏移量就是该记录的真实数据与页面中第 0 个字节之间的距离，这些地址偏移量被称为槽。

每个槽占用 2 字节，页目录就是由多个槽组成。

二、页目录的规定

在上一篇中，创建的表里存在 4 条数据，那么在页中还要算上 Infimum 和 Supremum，共 6 条记录。

这时候 InnoDB 会把它们分出 2 个组：

  • 第一组：只有一个 Infimum 记录
  • 第二组：剩下的 5 条记录

每个槽中，存放着每个组里最大的那条记录所在页面中的地址偏移量。

从图中，需要关注页目录的一些点：

  • 页目录有 2 个槽，说明记录被分为 2 个组。
  • Infimum 记录的 n_owned 属性值为 1，而 Supremum 的为 5。

为什么这 6 条记录要这样分？因为作者对于每组中的记录数量有规定：

  • 对于 Infimum 所在的分组只能有 1 条记录。
  • Supremum 所在的分组只能在 1~8 条之间。
  • 剩下的分组，记录条数范围只能是 4~8 之间。

三、页目录查找记录的过程

现在继续向测试表里插入 12 条数据，也就是说在页中共有 18 条记录。

然后这些记录就被分成了 5 个组，这里参考书籍上的示意图(只保留一些关键属性)：

现在，要查找主键是 6 的记录，要如何进行？

因为 5 个槽的编号分别为 0、1、2、3、4 挨着的，并且里面的主键值也都是从小到大进行排序的，可以使用二分法(不清楚的可以百度)，那么初始情况下 low=0，high=4：

  • 计算中间槽的位置，(0+4)/ 2=2，于是查看槽 2 对应记录的主键值为 8，因为 8 > 6，所以 high = 2，low 不变。
  • 重新计算中间槽位置，(0+2)/ 2=1，于是查看槽 1 对应记录的主键为4，因为 4 < 6，所以 high 不变，low = 1。
  • 因为 high - low = 1，所以确定主键值为6 的记录就在槽 2 对应的组中。接着找到该组中主键最小的记录，沿着单链表向后遍历，最终找到主键 6 的记录。

这里有个问题，槽对应的值都是这个组的主键最大的记录，如何找到组里最小的记录？比如槽 2 对应最大主键是 8 的记录，那如何找到最小记录。

解决办法是：

  • 通过槽 2 找到 槽 1 对应的记录，也就是主键为 4 的记录。
  • 主键为 4 的记录的下一条记录就是槽 2 当中主键最小的记录，可以找到主键 5。

总结

在一个数据页中查找指定主键值的记录，过程分为 2 步：

通过二分法确定该记录所在分组对应的槽，然后找到该槽所在分组中主键值最小的记录。

通过记录的 next_record 属性比那里该槽所在组的各个记录，最终找到目标记录。

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

以上就是Mysql InnoDB引擎中页目录和槽的查找过程的详细内容，更多关于Mysql InnoDB引擎页目录的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Mysql InnoDB引擎中的数据页结构详解

    Mysql InnoDB引擎中的数据页结构详解

    目录 Mysql InnoDB引擎数据页结构 一.页的简介 二.数据页的结构 三.记录在页中的存储结构 四.记录头信息 1. deleted_flag 2. min_rec_flag 3. n_owned 4. heap_no 5. record_type 6. next_record Mysql InnoDB引擎数据页结构 InnoDB 是 mysql 的默认引擎,也是我们最常用的,所以基于 InnoDB,学习页结构.而学习页结构,是为了更好的学习索引. 一.页的简介 页是 InnoDB 管理

  • MySQL的InnoDB存储引擎的数据页结构详解

    MySQL的InnoDB存储引擎的数据页结构详解

    目录 1InnoDB页的概念 2数据页的结构 3记录在页中的存储 4PageDirectory页目录 5FileHeader文件头部 6InnoDB页和记录的关系 7没有索引时查找记录 总结 1 InnoDB页的概念 InnoDB是一个将表中的数据存储在磁盘上的存储引擎,即使我们关闭并重启服务器,数据还是存在.而真正处理数据的过程发生在内存中,所以需要把磁盘中的数据加载到内存中,所以需要把磁盘中的数据加载到内存中.如果处理写入和修改请求,还需要将内存中的内容刷新到磁盘上.而我们知道读写磁盘的速度

  • 详解MySql中InnoDB存储引擎中的各种锁

    详解MySql中InnoDB存储引擎中的各种锁

    目录 什么是锁 InnoDB存储引擎中的锁 锁的算法 行锁的3种算法 幻像问题 锁的问题 脏读 不可重复读 丢失更新 死锁 什么是锁 现实生活中的锁是为了保护你的私有物品,在数据库中锁是为了解决资源争抢的问题,锁是数据库系统区别于文件系统的一个关键特性.锁机制用于管理对共享资源的并发访. 数据库系统使用锁是为了支持对共享资源进行并发访问,提供数据的完整性和一致性 InnoDB存储引擎区别于MyISAM的两个重要特征就是:InnoDB存储引擎支持事务和行级别的锁,MyISAM只支持表级别的锁 In

  • MySQL的存储引擎InnoDB和MyISAM

    MySQL的存储引擎InnoDB和MyISAM

    目录 1.MyISAM底层存储 1.1MyISAM底层存储(非聚集索引方式) 1.2InnoDB底层存储(聚集索引方式) 2.InnoDB与MyISAM简介 3.MyISAM与InnoDB的比较 4.什么时候用MyISAM数据存储引擎?什么时候用InnoDB数据存储引擎? 1.MyISAM底层存储 (非聚集索引方式)与InnoDB底层存储(聚集索引方式) 1.1MyISAM底层存储(非聚集索引方式) Myisam 创建表后生成的文件有三个: frm:创建表的语句 MYD:表里面的数据文件(myi

  • Mysql InnoDB引擎的索引与存储结构详解

    Mysql InnoDB引擎的索引与存储结构详解

    前言 在Oracle 和SQL Server等数据库中只有一种存储引擎,所有数据存储管理机制都是一样的. 而MySql数据库提供了多种存储引擎.用户可以根据不同的需求为数据表选择不同的存储引擎,用户也可以根据自己的需要编写自己的存储引擎. MySQL主要存储引擎的区别 MySQL默认的存储引擎是MyISAM,其他常用的就是InnoDB,另外还有MERGE.MEMORY(HEAP)等. 主要的几个存储引擎 MyISAM管理非事务表,提供高速存储和检索,以及全文搜索能力. MyISAM是Mysql的

  • Mysql InnoDB引擎中页目录和槽的查找过程

    Mysql InnoDB引擎中页目录和槽的查找过程

    目录 Mysql InnoDB引擎页目录 一.页目录和槽 二.页目录的规定 三.页目录查找记录的过程 总结 Mysql InnoDB引擎页目录 一.页目录和槽 接上一篇,现在知道记录在页中按照主键大小顺序串成了单链表. 那么我使用主键查询的时候,最顺其自然的办法肯定是从第一条记录,也就是 Infrimum 记录开始,一直向后找,只要存在总会找到.这种在数据量少的时候还好说,一旦数据多了,遍历耗时一定非常长. 于是,作者又想到了一个好办法,灵感来自于书本中的目录.我们翻书的时候想查找一些内容,就会

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

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

    目录 Mysql InnoDB B+树索引目录项记录管理 一.目录项记录页 二.当目录项记录页也变多后 三.B+ 树 Mysql InnoDB B+树索引目录项记录管理 接上一篇内容,InnoDB 的作者想到一种更灵活的方式来管理所有目录项,是什么? 一.目录项记录页 其实这些用户目录项与用户记录很像,只是目录项中的两个列记录的是主键和页号而已,那么就可以复用之前存储用户记录的数据页来存储目录项. 为了区分用户记录和目录项,仍然使用 record_type 这个属性,当值为 1 时,表示目录项记

  • MySQL InnoDB引擎的缓存特性详解

    MySQL InnoDB引擎的缓存特性详解

    目录 1. 背景 2. 存储器性能差异 3. Buffer Pool 4. Free链表 5. Flush链表 6. LRU链表 7. 其它 1. 背景 对于各种用户数据.索引数据等各种数据都是需要持久化存储到磁盘,然后以“页”为单位进行读写. 相对于直接读写缓存,磁盘IO的成本相当高昂. 对于读取的页面数据,并不是使用完就释放掉,而是放到缓冲区,因为下一次操作有可能还需要读区该页面. 对于修改过的页面数据,也不是马上同步到磁盘,也是放到缓冲区,因为下一次有可能还会修改该页面的数据. 但是缓存的

  • 详解MySQL下InnoDB引擎中的Memcached插件

    前些年,HandlerSocket的横空出世让人们眼前一亮,当时我还写了一篇文章介绍了其用法梗概,时至今日,由于种种原因,HandlerSocket并没有真正流行起来,不过庆幸的是MySQL官方受其启发,研发了基于InnoDB的Memcached插件,总算是在MySQL中延续了NoSQL的香火,以前单独架设Memcached服务器不仅浪费了内存,而且还必须自己维护数据的不一致问题,有了Memcached插件,这些问题都不存在了,而且借助MySQL本身的复制功能,我们可以说是变相的实现了Memca

  • MySQL存储引擎中MyISAM和InnoDB区别详解

    InnoDB和MyISAM是许多人在使用MySQL时最常用的两个表类型,这两个表类型各有优劣,视具体应用而定.基本的差别为:MyISAM类型不支持事务处理等高级处理,而InnoDB类型支持.MyISAM类型的表强调的是性能,其执行数度比InnoDB类型更快,但是不提供事务支持,而InnoDB提供事务支持以及外部键等高级数据库功能. 以下是一些细节和具体实现的差别: ◆1.InnoDB不支持FULLTEXT类型的索引. ◆2.InnoDB 中不保存表的具体行数,也就是说,执行select coun

  • MySQL存储引擎中的MyISAM和InnoDB区别详解

    MySQL存储引擎中的MyISAM和InnoDB区别详解

    在使用MySQL的过程中对MyISAM和InnoDB这两个概念存在了些疑问,到底两者引擎有何分别一直是存在我心中的疑问.为了解开这个谜题,搜寻了网络,找到了如下信息: MyISAM是MySQL的默认数据库引擎(5.5版之前),由早期的ISAM(Indexed Sequential Access Method:有索引的顺序访问方法)所改良.虽然性能极佳,但却有一个缺点:不支持事务处理(transaction).不过,在这几年的发展下,MySQL也导入了InnoDB(另一种数据库引擎),以强化参考完

  • MYSQL数据库Innodb 引擎mvcc锁实现原理

    MYSQL数据库Innodb 引擎mvcc锁实现原理

    目录 1 数据库设置隔离级别 2 数据库表以及案例操作 3 mvcc 实现原理 4 ACID 的实现 前言: 大家都知道在java 开发过程中,会经常用到锁,在java 代码中,我们都知道锁是加在对象头上的,在java对象布局中有锁的标志位.程序通过判断锁的标志位来获取加锁的情况.但是在mysql 中,锁的实现原理是什么呢.可能大家都听过 mvcc,但是mvcc 的实现原理是什么呢,可能就说不太清楚了,本文就以实例说明来mvcc 的实现原理. 1 数据库设置隔离级别 我们都知道数据库的隔离级别可

  • Mysql InnoDB聚簇索引二级索引联合索引特点

    Mysql InnoDB聚簇索引二级索引联合索引特点

    目录 一.聚簇索引 特点 1 特点 2 二.二级索引 三.联合索引 接上一篇内容:https://www.jb51.net/article/249934.htm 一.聚簇索引 其实之前内容中介绍的 B+ 树就是聚簇索引. 这种索引不需要我们显示地使用 INDEX 语句去创建,InnoDB 引擎会自动创建.另外,在 InnoDB 引擎中,聚簇索引就是数据的存储方式. 它有 2 个特点: 特点 1 使用记录主键值的大小进行记录和页的排序. 其中又包含了下面 3 个点: 页(包括叶节点和内节点)内的记

随机推荐