关于innodb中查询的定位方法

为什么谈及定位方法，因为在innodb中，比如一个插入语句我们需要定位在哪里插入(PAGE_CUR_LE)，比如一个查询语句我们需要定位到其第一个需要读取数据的位置，因此定位方法是查询的根本。而找到这个记录位置后实际上是用一个叫做page_cur_t结构体进行存储，暂且叫他cursor游标

其中包含了本index的数据字典类容、实际的数据、记录所在块的信息等，下面我具体谈一下定位方法，同时结合源码来看它具体的实现。

开发云主机域名我们先来明确一下概念：

可自行参考运维内参等其他书籍，这里就在简单描述到这里，本文会出现相关术语。

在innodb中的常用的search mode有如下几个

我们来讨论一个问题考虑如下有序的数组

如果我们查询>=3(PAGE_CUR_GE)和

如果我们查询3(PAGE_CUR_G),那么自然我们需要将位置定位到3到4之间我们且用3-4表示

那么我们将这里的区间两个值记为low-high

仔细分析后我们发现另外一个规律

为什么讲这个东西，因为这两个规律在innodb记录定位中起到了关键作用，也直接影响到了innodb记录查找的二分算法的实现方式。

大家在源码中能看到matched_fields和matched_bytes两个值，那么他们代表什么意思呢？

以int类型为例，因为在函数cmp_dtuple_rec_with_match_bytes是逐个字段逐个字节进行比较的，关键代码如下

比如int 2,int 3在innodb中内部表示为0X80000002和0X80000003,如果他们进行比较那么最终此field的比较为不相等(-1),那么matched_fields=0但是

具体可以参考一下源码，这里不再过多解释

为什么叫做再析，因为如运维内参已经对本函数进行了分析，这里主要分析查询模式对二分法实现的影响，并且用图进行说明你会有新的感悟！当然如果你对什么slot还不清楚请自行参考运维内参

简单的说page_cur_search_with_match_bytes会调用cmp_dtuple_rec_with_match_bytes函数进行元组和记录之间的比较，而块内部比较方法就是先对所有的slot进行二分查找确定到某个slot以快速缩小范围，然后在对slot内部使用类似二分查找的方法等到记录，我们主要来分析一下slot内部的类二分法，因为它完全是我们查询模式中两个规律的完美体现，如下简化的代码片段以及我写的注释：

注意一个slot的own记录为最多8条如下定义:

如果大于了8则进行分裂

下面我们画一个slot内部定位的图，我们以如下有序数据为例，假设每一个数字代表一个记录(rec)

我们可以看到有大量重复的记录，但是本算法也可以进行精确的定位，我们约定:

mid为2显然已经等于了元组的中的2，如图

但是查询模式为PAGE_CUR_G 做low_rec_match操作、并且将mid取向下一条记录后如图

mid为2显然已经等于了元组的中的2，但是查询模式为PAGE_CUR_G做low_rec_match后、并且将mid取向下一条记录如图

mid为3显然已经大于了元组中的2，做up_rec_match后我们发现记录定位成功，为low 2-high 3。page_rec_get_next_const(low_rec) == up_rec 循环退出如图

因为我们的查询模式是PAGE_CUR_G所以我们执行page_cur_position(up_rec, block, cursor);取high值如图

mid为2显然小于元组的中的3，如图

做low_rec_match操作、并且将mid取向下一条记录后如图

mid为2显然小于元组的中的3，做low_rec_match操作、并且将mid取向下一条记录后如图