Mysql InnoDB引擎中页目录和槽的查找过程
作者:把苹果咬哭的测试笔记 发布时间:2024-01-14 09:32:28
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。
来源:https://blog.csdn.net/wessonlan/article/details/124813000
猜你喜欢
- 网页广告 Banner 设计图文手册:采用以下要点来改善你的BANNER。广告并不便宜。 确信你的广告被第一时间读到。使用像这样的Sans
- 前言前几天逛github发现了一个有趣的并发库-conc,其目标是:更难出现goroutine泄漏处理panic更友好并发代码可读性高从简介
- 目录常规加载QImageReader 类昨天写程序遇到一个问题,pyqt5 加载常规的图片完全可以显示。可当加载超清的高分辨率图片时,只能显
- kmp算法KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特
- 无论是我们上学时还之后的工作中,基本都需要用到电子证件照片,这类照片基本都对照片尺寸、背景色有要求,本文我们来看一下如何只用不到 20 行
- 如何实现质数求和生活中很多问题是需要用数学来解决的,比如说要是做一栋房子,各方面的数据都要计算,要用多少材料,长宽高多少等,简单地说,运算就
- 1、python大量的库为数据分析提供了完整的工具集2、比起MATLAB、R语言等其他主要用于数据分析语言,python语言功能更加健全3、
- 本文实例讲述了python 协程 gevent原理与用法。分享给大家供大家参考,具体如下:geventgreenlet已经实现了协程,但是这
- 将时间信息“2018-02-04 18:23:35“ 解析成字典形式的结果如:{‘year':2018,‘month
- Pycharm运行程序时,控制台输出PyDev console:starting1、问题:写好程序后,点击Run运行,控制台如下图所示提示P
- 类:定义一件事物的抽象特点。对象:类的 实例。成员变量 − 定义在类内部的变量。该变量的值对外是不可见的,但是可以通过成
- 今天看关于Git的博客,发现总结关于Git仓库的文档,写的思路很清晰。可以和前一篇文章,对照的看,可以更加清晰理解。git-referenc
- 表结构: CREATE TABLE [dbo].[Xtest]( [ID] [bigint] IDENTITY(1,1) NOT NULL,
- reader.html<html><head><meta http-equiv=&quo
- php 如何获取请求的xml数据,对方通过http协议post提交过来xml数据,php如何获取到这些数据呢?<?php $xml_d
- SELECT *FROM ( &n
- 目录1. 简介2. 示例代码13. 示例代码24. 启动异常1. 简介Gunicorn(Green Unicorn)是给Unix用的WSGI
- 1.1.1 摘要 Join是关系型数据库系统的重要操作之一,SQL Server中包含的常用Join:内联接、外联接和交叉联接等。如果我们想
- 数据库中数据展示:使用python代码实现:# Requires pymongo 3.6.0+from pymongo import Mon
- 本文实例为大家分享了python七夕浪漫表白的具体代码,供大家参考,具体内容如下from turtle import *from time