原创转载请注明出处
源码版本 5.7.14
涉及源码文件
page0cur.cc
page0page.h
page0page.cc
rem0cmp.cc 为什么谈及定位方法，因为在innodb中，比如一个插入语句我们需要定位在哪里插入(PAGE_CUR_LE)，比如一个查询语句我们需要定位到其第一个需要读取数据的位置，因此定位方法是查询的根本。而找到这个记录位置后实际上是用一个叫做page_cur_t结构体进行存储，暂且叫他cursor游标
struct page_cur_t{
const dict_index_t* index;
rec_t* rec;
ulint* offsets;
buf_block_t* block;
}; 其中包含了本index的数据字典类容、实际的数据、记录所在块的信息等，下面我具体谈一下定位方法，同时结合源码来看它具体的实现。
我们先来明确一下概念：
- 记录(rec)：通常为存储在内存中物理记录的完全拷贝，通常用一个unsigned char* 指针指向整个记录
- 元组(dtuple)：物理记录的逻辑体现，他就复杂得多，但是一个记录(rec)对应一个元组(dtuple),由dtuple_t结构体表示，其中每一个field由一个dfield_t结构体表示，数据存储在dfied_t的一个叫做void* data的指针中
可自行参考运维内参等其他书籍，这里就在简单描述到这里，本文会出现相关术语。
一、查询模式(search mode)
在innodb中的常用的search mode有如下几个
enum page_cur_mode_t {
PAGE_CUR_UNSUPP = 0,
PAGE_CUR_G = 1,
PAGE_CUR_GE = 2,
PAGE_CUR_L = 3,
PAGE_CUR_LE = 4,
}; - PAGE_CUR_G(>)
- PAGE_CUR_GE(>=)
- PAGE_CUR_L(<)
- PAGE_CUR_LE(<=)
我们来讨论一个问题考虑如下有序的数组
1,2,3,3,4,5,6,7 规律1:
如果我们查询>=3(PAGE_CUR_GE)和<3(PAGE_CUR_L),那么自然我们需要将位置定位到2到3之间我们且用2-3表示
- 如果是>=3那么我们需要将记录定位到3及[3(第一个),正无穷)
-
如果是<3那么我们需要将记录定位到2及（负无穷,2]
也就是说>=3和<3定位的区间是相同的2-3
如果我们查询<=3(PAGE_CUR_LE)和>3(PAGE_CUR_G),那么自然我们需要将位置定位到3到4之间我们且用3-4表示
- 如果是<=3那么我们需要将记录定位到3及(负无穷,3(最后一个)]
-
如果是>3那么我们需要将记录定位到4及[4,正无穷)
也就是说<=3和>3定位的区间是相同的3-4
那么我们将这里的区间两个值记为low-high
规律2:
仔细分析后我们发现另外一个规律
- (>) PAGE_CUR_G和(>=) PAGE_CUR_GE 都是取high
- (< )PAGE_CUR_L和(<=) PAGE_CUR_LE 都是取low
为什么讲这个东西，因为这两个规律在innodb记录定位中起到了关键作用，也直接影响到了innodb记录查找的二分算法的实现方式。
二、matched_fields和matched_bytes
大家在源码中能看到matched_fields和matched_bytes两个值，那么他们代表什么意思呢？
以int类型为例，因为在函数cmp_dtuple_rec_with_match_bytes是逐个字段逐个字节进行比较的，关键代码如下
while (cur_field < n_cmp) {
rec_byte = *rec_b_ptr++;
dtuple_byte = *dtuple_b_ptr++;} 比如int 2,int 3在innodb中内部表示为0X80000002和0X80000003,如果他们进行比较那么最终此field的比较为不相等(-1),那么matched_fields=0但是
- 0X 800000 02
-
0X 800000 03
我们能够发现其中有3个字节是相同的及0X80 0X00 0X00 所以matched_bytes=3
简单的说matched_fields为相同field数量,如果field不相同则会返回相同的字节数。
当然cmp_dtuple_rec_with_match_bytes对不同数据类型的比较方式也不相同如下:
switch (type->mtype) {
case DATA_FIXBINARY:
case DATA_BINARY:
case DATA_INT:
case DATA_SYS_CHILD:
case DATA_SYS:
break;
case DATA_BLOB:
if (type->prtype & DATA_BINARY_TYPE) {
break;
}
default:
ret = cmp_data(type->mtype, type->prtype,
dtuple_b_ptr, dtuple_f_len,
rec_b_ptr, rec_f_len);
if (!ret) {
goto next_field;
}
cur_bytes = 0;
goto order_resolved;
} 具体可以参考一下源码，这里不再过多解释
三、块内二分查询方法再析
为什么叫做再析，因为如运维内参已经对本函数进行了分析，这里主要分析查询模式对二分法实现的影响，并且用图进行说明你会有新的感悟！当然如果你对什么slot还不清楚请自行参考运维内参
简单的说page_cur_search_with_match_bytes会调用cmp_dtuple_rec_with_match_bytes函数进行元组和记录之间的比较，而块内部比较方法就是先对所有的slot进行二分查找确定到某个slot以快速缩小范围，然后在对slot内部使用类似二分查找的方法等到记录，我们主要来分析一下slot内部的类二分法，因为它完全是我们查询模式中两个规律的完美体现，如下简化的代码片段以及我写的注释：
while (page_rec_get_next_const(low_rec) != up_rec) { //如果low_rec和up_rec相差1则结束循环，否则继续
mid_rec = page_rec_get_next_const(low_rec);//这里并没有除以2作为mid_rec而是简单的取下一行，因为rec是单链表这样显然很容易完成
ut_pair_min(&cur_matched_fields, &cur_matched_bytes,
low_matched_fields, low_matched_bytes,
up_matched_fields, up_matched_bytes);
offsets = rec_get_offsets(
mid_rec, index, offsets_,
dtuple_get_n_fields_cmp(tuple), &heap);//获得记录的各个字段的偏移数组
cmp = cmp_dtuple_rec_with_match_bytes(
tuple, mid_rec, index, offsets,
&cur_matched_fields, &cur_matched_bytes);//进行比较 0为相等 1 元组大于记录 -1记录大于元组，并且传出field和bytes
if (cmp > 0) { //如果元组大于mid_rec记录
low_rec_match://当然简单的将mid_rec指针赋予给low_rec即可
low_rec = mid_rec;
low_matched_fields = cur_matched_fields;
low_matched_bytes = cur_matched_bytes;
} else if (cmp) { //如果元组小于mid_rec记录
up_rec_match://当然简单的将mid_rec指针赋予给up_rec即可，这一步可以跳过很多记录
up_rec = mid_rec;
up_matched_fields = cur_matched_fields;
up_matched_bytes = cur_matched_bytes;
}
//下面是相等情况的判断非常关键符合我们规律1算法
//如果元组等于mid_rec
else if (mode == PAGE_CUR_G || mode == PAGE_CUR_LE //如果是>(PAGE_CUR_G)和<=(PAGE_CUR_LE)
) {
goto low_rec_match; //执行low_rec_match
} else //如果是>=(PAGE_CUR_GE)和<(PAGE_CUR_L)
{
goto up_rec_match;//执行up_rec_match
}
}
//下面体现我们的规律2算法
//如果是> PAGE_CUR_G和>= PAGE_CUR_GE 都是取high
//如果是< PAGE_CUR_L和<= PAGE_CUR_LE 都是取low
//因为是enum类型直接比较
if (mode <= PAGE_CUR_GE) {
page_cur_position(up_rec, block, cursor);
} else {
page_cur_position(low_rec, block, cursor);
}
*iup_matched_fields = up_matched_fields;
*iup_matched_bytes = up_matched_bytes;
*ilow_matched_fields = low_matched_fields;
*ilow_matched_bytes = low_matched_bytes; 注意一个slot的own记录为最多8条如下定义:
#define PAGE_DIR_SLOT_MAX_N_OWNED 8
#define PAGE_DIR_SLOT_MIN_N_OWNED 4 如果大于了8则进行分裂
if (n_owned == PAGE_DIR_SLOT_MAX_N_OWNED) {
page_dir_split_slot(
page, NULL,
page_dir_find_owner_slot(owner_rec));
} 下面我们画一个slot内部定位的图，我们以如下有序数据为例，假设每一个数字代表一个记录(rec)
1 2 2 2 3 3 4 4 我们可以看到有大量重复的记录，但是本算法也可以进行精确的定位，我们约定:
- 红色箭头为最后定位到的值
- 黄色箭头为mid rec
- 黑色箭头分别表示low rec\high rec
如果是我们要定位到>2,那么我们明显要定位到2-3同时取high值3，我们用源码中的代码推导出整个过程如下：
-
mid为2显然已经等于了元组的中的2，如图
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
历年真题答案解析
备考技巧名师总结
高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1148
183.71 KB下载数642
644.84 KB下载数2756
相关文章
发现更多好内容猜你喜欢
AI推送时光机关于innodb中查询的定位方法
数据库2024-04-02mongodb定位查询的方法是什么
数据库2023-09-06关于MySQL中的查询开销查看方法详解
数据库2024-04-02关于SQL查询语句关键字方法
数据库2024-04-02MySQL定位并优化慢查询sql的方法是什么
数据库2023-06-22关于 MySQL 嵌套子查询中无法关联主表字段问题的解决方法
数据库2022-12-26关于查询MySQL字段注释的5种方法总结
数据库2024-04-02关于MySQL嵌套子查询中无法关联主表字段问题的解决方法
数据库2022-12-26mysql中join关联查询的方法是什么
![mysql中join关联查询的方法是什么]()
数据库2024-05-21vue中关于@media媒体查询的使用
数据库2022-11-13查询存储过程中特定字符的方法
数据库2022-11-15相对于绝对定位的参照方法
![相对于绝对定位的参照方法]()
数据库2024-01-23关于MyBatis模糊查询的几种实现方式
数据库2023-05-18关于找不到mss32.dll文件或无法定位的问题解决方法
数据库2023-09-06MyBatis自定义映射关系和关联查询实现方法详解
数据库2023-05-15DoytoQuery中关于N+1查询问题解决方案详解
数据库2022-12-27mysql位运算查询优化的方法是什么
![mysql位运算查询优化的方法是什么]()
数据库2024-04-02php数组查询元素位置的实例方法
数据库2024-04-02咦！没有更多了？去看看其它编程学习网 内容吧
