本文在介绍 MySQL 内存中记录、页、索引、游标的数据结构的基础上,通过简单分析插入操作过程中行格式的转换介绍了不同数据结构的关系,其中不涉及加锁相关逻辑。
InnoDB 存储引擎基于记录(record)存储,表明记录是根据行(row)格式存储。
MySQL 中有行格式有以下三种存储方式:
因此:
个人理解存取数据时完成二进制到“字符串”的相互转换(忽略其他数据类型),相当于客户端与服务端交互时的编码与解码。
内存中逻辑记录与其中的字段分别对应数据结构 dtuple_t 与 dfield_t。
结构体定义如下所示。
/** Structure for an SQL data tuple of fields (logical record) */
struct dtuple_t {
ulint n_fields; /*!< number of fields in dtuple */
ulint n_fields_cmp; /*!< number of fields which should
be used in comparison services
of rem0cmp.*; the index search
is performed by comparing only these
fields, others are ignored; the
default value in dtuple creation is
the same value as n_fields */
dfield_t* fields; /*!< fields */
UT_LIST_NODE_T(dtuple_t) tuple_list;
/*!< data tuples can be linked into a
list using this field */
};
其中:
数据结构 dfield_t 中保存列的信息。
/** Structure for an SQL data field */
struct dfield_t{
void* data; /*!< pointer to data */
unsigned ext:1; /*!< TRUE=externally stored, FALSE=local */
unsigned len; /*!< data length; UNIV_SQL_NULL if SQL null */
dtype_t type; /*!< type of data */
};
其中:
物理记录由 rec_t 数据结构表示,字节类型。
/* We define the physical record simply as an array of bytes */
typedef byte rec_t;
页和记录类似同样可以分为以下两种形式:
页分多种类型,比如 index page、undo log page 等,本文关注的是 index page。
由于 InnoDB 是索引组织树,索引即数据,因此可以将索引页理解为数据页。
InnoDB 中页是一个无序堆,因此页中的记录无序存放,记录间通过 record header 中的 next record 组成单向链表。
buffer pool 中与页相关的有两个数据结构,包括 buf_block_t 和 buf_page_t 。
buf_block_t 是数据页控制体的一种。
/** The buffer control block structure */
struct buf_block_t{
buf_page_t page; /*!page_hash can point
to buf_page_t or buf_block_t */
byte* frame;
BPageLock lock; /*!< read-write lock of the buffer frame */
其中:
buf_page_t 称为数据页控制体。
/** The common buffer control block structure
for compressed and uncompressed frames */
class buf_page_t {
public:
page_id_t id; // page id
buf_page_t* hash; /*!page_hash or
buf_pool->zip_hash */
lsn_t newest_modification; // 当前Page最新修改lsn
lsn_t oldest_modification; // 当前Page最老修改lsn,即第一条修改lsn
};
其中:
索引是基于以空间换时间的思想用于加速查询的数据结构。
InnoDB 中索引基于 B+ 树实现,因此每个索引都是一棵 B+ 树。索引用于组织页,页用于组织行记录。
每个 B+ 树索引在内存中对应数据结构 dict_index_t。
/** Data structure for an index. Most fields will be
initialized to 0, NULL or FALSE in dict_mem_index_create(). */
struct dict_index_t{
index_id_t id; /*!< id of the index */
mem_heap_t* heap; /*!< memory heap */
id_name_t name; /*!< index name */
const char* table_name;/*!< table name */
dict_table_t* table; /*!< back pointer to table */
unsigned space:32;
/*!< space where the index tree is placed */
unsigned page:32;/*!< index tree root page number */
unsigned allow_duplicates:1;
/*!< if true, allow duplicate values
even if index is created with unique
constraint */
unsigned n_uniq:10;/*!< number of fields from the beginning
which are enough to determine an index
entry uniquely */
unsigned n_def:10;/*!< number of fields defined so far */
unsigned n_fields:10;/*!< number of fields in the index */
unsigned n_nullable:10;/*!< number of nullable fields */
dict_field_t* fields; /*!< array of field descriptions */
};
其中:
通过 B+ 树索引进行查找(lookup)是最为常见的操作,具体通过游标实现。
游标是一个逻辑概念,无论是写入还是查询,都需要在 B+ 树上遍历至某个位置,具体到某个 block 上的某个 record。
InnoDB 中通过 cursor search 实现 B+ 树的查找,每个 open 一个 cursor 都会开启一个从 B+ 树 root 结点搜索到指定层级的 record 的搜索过程。
cursor 分为以下两种:
page cursor 在定位(lookup)到记录后,再通过查询模式(search mode)再进行向前或向后的记录扫描(scan)。
比如对于一个主键的范围查询,首先需要定位第一条记录,然后进行记录的顺序扫描。
InnoDB 中定义了四种查询模式:
/* Build the template used in converting quickly between
the two database formats */
build_template(true);
}
/* Step-5: Execute insert graph that will result in actual insert. */
// 插入数据
error = row_insert_for_mysql((byte*) record, m_prebuilt);
}
其中:
unsigned char 数据类型经常被用于处理原始字节数据,比如在进行二进制文件读写、网络通信、处理图像数据、编码转换或者其他需要以字节为单位操作的场景中。利用 unsigned char 可以确保不会有负值出现,这在与二进制数据和位操作打交道时非常有用。
typedef unsigned char uchar; /* Short for unsigned char */
/* Note that inside MySQL 'byte' is defined as char on Linux! */
#define byte unsigned char
m_prebuilt 变量是 row_prebuilt_t 结构体指针类型,其中部分成员如下所示,包括表、索引、游标等各种信息。
/** Save CPU time with prebuilt/cached data structures */
row_prebuilt_t* m_prebuilt;
/** A struct for (sometimes lazily) prebuilt structures in an Innobase table
handle used within MySQL; these are used to save CPU time. */
struct row_prebuilt_t {
dict_table_t* table; /*!< Innobase table handle */
dict_index_t* index; /*!< current index for a search, if any */
trx_t* trx; /*!< current transaction handle */
unsigned n_template:10; /*!< number of elements in the
template */
ins_node_t* ins_node; /*!< Innobase SQL insert node
used to perform inserts
to the table */
byte* ins_upd_rec_buff;/*!< buffer for storing data converted
to the Innobase format from the MySQL
format */
mysql_row_templ_t* mysql_template;/*!< template used to transform
rows fast between MySQL and Innobase
formats; memory for this template
is not allocated from 'heap' */
btr_pcur_t* pcur; /*!< persistent cursor used in selects
and updates */
};
其中:
row_prebuilt_t 结构体与 build_template 函数的作用参考 chatgpt:
在 InnoDB 存储引擎的设计中,row_prebuilt_t和build_template都是实现 SQL 层与存储引擎层之间高效数据交互的重要组成部分。一方面,row_prebuilt_t作为一个操作上下文,保存了完成某个表操作所需的所有信息;另一方面,build_template则通过预先构建模板来优化数据列的读取和转换过程。
row_insert_for_mysql 函数中调用 row_insert_for_mysql_using_ins_graph 函数,其中将 Server 层的记录格式转换为 InnoDB 的记录格式,具体是从 byte 转换为 dtuple_t。
// storage/innobase/row/row0mysql.cc
static
dberr_t
row_insert_for_mysql_using_ins_graph(
const byte* mysql_rec, /* row in the MySQL format */
row_prebuilt_t* prebuilt) /* prebuilt struct in MySQL handle */
{
que_thr_t* thr;
ins_node_t* node = prebuilt->ins_node;
// 主要构造用于执行插入操作的 2 个对象:
// 1. ins_node_t 对象,保存在 prebuilt->ins_node 中
// 2. que_fork_t 对象,保存在 prebuilt->ins_graph 中
row_get_prebuilt_insert_row(prebuilt);
node = prebuilt->ins_node;
// 把 server 层的记录格式转换为 InnoDB 的记录格式
row_mysql_convert_row_to_innobase(node->row, prebuilt, mysql_rec,
&blob_heap);
thr->run_node = node;
thr->prev_node = node;
// 执行插入操作,插入记录到主键索引、二级索引(包含唯一索引、非唯一索引)
/*插入记录*/
row_ins_step(thr);
}
其中:
这里又出现了一个重要的结构体 ins_node_t,该结构体部分成员如下所示。
/* Insert node structure */
struct ins_node_t{
dtuple_t* row; /*!< row to insert */
dict_table_t* table; /*!< table where to insert */
sel_node_t* select; /*!< select in searched insert */
que_node_t* values_list;/* list of expressions to evaluate and
insert in an INS_VALUES insert */
ulint state; /*!< node execution state */
dict_index_t* index; /*!< NULL, or the next index where the index
entry should be inserted */
dtuple_t* entry; /*!< NULL, or entry to insert in the index;
after a successful insert of the entry,
this should be reset to NULL */
}
其中:
row_mysql_convert_row_to_innobase 函数中遍历索引的所有列(prebuilt->n_template)进行赋值。
static
void
row_mysql_convert_row_to_innobase(
/*==============================*/
dtuple_t* row, /*!< in/out: Innobase row where the
field type information is already
copied there! */
row_prebuilt_t* prebuilt, /*!< in: prebuilt struct where template
must be of type ROW_MYSQL_WHOLE_ROW */
const byte* mysql_rec, /*!< in: row in the MySQL format; */
mem_heap_t** blob_heap) /*!< in: FIX_ME, remove this after
server fixes its issue */
{
const mysql_row_templ_t*templ;
for (i = 0; i n_template; i++) {
templ = prebuilt->mysql_template + i;
// 获取 field
dfield = dtuple_get_nth_field(row, n_col);
// 格式转换,从 rec 写入 dtuple_t
row_mysql_store_col_in_innobase_format(
/* dfield_t* dfield, call to set field */
dfield,
/* byte* buf, buffer for a converted integer value */
prebuilt->ins_upd_rec_buff + templ->mysql_col_offset,
/* ibool row_format_col, TRUE if the mysql_data is from a MySQL row, FALSE if from a MySQL key value; */
TRUE,
/* byte* mysql_data, MySQL row format data */
mysql_rec + templ->mysql_col_offset,
/* ulint col_len, MySQL column length */
templ->mysql_col_len,
/*!table));
}
其中:
const byte* ptr = mysql_data;
const dtype_t* dtype;
ulint type;
dtype = dfield_get_type(dfield);
type = dtype->mtype;
// 计算 col_len
...
dfield_set_data(dfield, ptr, col_len);
其中:
/* Sets pointer to the data and length in a field. */
UNIV_INLINE
void
dfield_set_data(
/*============*/
dfield_t* field, /*!< in: field */
const void* data, /*!< in: data */
ulint len) /*!data = (void*) data;
field->ext = 0;
field->len = static_cast(len);
}
其中:
到这里完整的行数据索引元组格式 dtuple_t* row dtuple_t 准备好了,但由于 InnoDB 是索引组织树,因此还需要将数据保存到索引元组格式 dtuple_t* entry 中。
row_ins_step 函数中创建 ins_node_t 并调用 row_ins 函数。
// 创建 ins_node_t
node = static_cast(thr->run_node);
// 给表加上意向锁
err = lock_table(0, node->table, LOCK_IX, thr);
/* DO THE CHECKS OF THE CONSISTENCY CONSTRAINTS HERE */
// 调用 row_ins() 插入记录到主键索引、二级索引
err = row_ins(node, thr);
row_ins 函数中遍历表的每个 index,插入 index entry。
// 遍历所有索引,向每个索引中插入记录
while (node->index != NULL) {
/* 向索引中插入记录 */
err = row_ins_index_entry_step(node, thr);
// 插入记录到主键索引或二级索引成功后获取下一个索引
// node->index、entry 指向表中的下一个索引
node->index = dict_table_get_next_index(node->index);
node->entry = UT_LIST_GET_NEXT(tuple_list, node->entry);
其中:
row_ins_index_entry_step 函数中向指定索引中插入记录。
// storage/innobase/row/row0insert.cc
/* Inserts a single index entry to the table. */
static MY_ATTRIBUTE((nonnull, warn_unused_result))
dberr_t
row_ins_index_entry_step(
/*=====================*/
ins_node_t* node, /*!< in: row insert node */
que_thr_t* thr) /*!index, node->entry, node->row);
/*插入索引项*/
err = row_ins_index_entry(node->index, node->entry, thr);
}
其中:
/** Sets the values of the dtuple fields in entry from the values of appropriate columns in row. */
dberr_t
row_ins_index_entry_set_vals(
const dict_index_t* index,
dtuple_t* entry,
const dtuple_t* row)
{
n_fields = dtuple_get_n_fields(entry);
for (i = 0; i col->ind);
len = dfield_get_len(row_field);
// 写入 field
dfield_set_data(field, dfield_get_data(row_field), len);
}
其中:
到这里每个索引的数据也准备好了,但是还不知道数据插入的位置,理论上是插在最后一个小于等于该 dtuple 的 rec_t 后。
row_ins_index_entry 函数中以插入主键索引为例。
row_ins_clust_index_entry_low 函数中以乐观插入为例。
// storage/innbase/row/row0ins.cc
dberr_t
row_ins_clust_index_entry_low(
/*==========================*/
ulint flags, /*!< in: undo logging and locking flags */
ulint mode, /*!< in: BTR_MODIFY_LEAF or BTR_MODIFY_TREE,
depending on whether we wish optimistic or
pessimistic descent down the index tree */
dict_index_t* index, /*!< in: clustered index */
ulint n_uniq, /*!n_uniq */
dtuple_t* entry, /*!< in/out: index entry to insert */
ulint n_ext, /*!< in: number of externally stored columns */
que_thr_t* thr, /*!< in: query thread */
bool dup_chk_only)
/*!thr = thr;
rec_t* insert_rec;
/* 乐观插入 */
err = btr_cur_optimistic_insert(
flags, cursor, &offsets, &offsets_heap,
entry, &insert_rec, &big_rec,
n_ext, thr, &mtr);
}
其中:
btr_pcur_open 函数中调用 btr_cur_search_to_nth_level 函数用于自顶向下查找整个 B-tree。
page_cursor = btr_cur_get_page_cur(cursor);
// 初始的,获得索引的根节点(space_id,page_no)
const ulint space = dict_index_get_space(index);
const page_size_t page_size(dict_table_page_size(index->table));
/* Start with the root page. */
// 从 dict_index_t 元信息中拿到 root page 在物理文件的 page no(默认是 4)
page_id_t page_id(space, dict_index_get_page(index));
// 从 buffer_pool 中根据 page no 拿 page(buf_page_get_gen),buffer pool 模块会根据 page 是否被缓存来决定是从内存中还是磁盘中读取,并根据加锁策略对 page 加锁
block = buf_page_get_gen(page_id, page_size, rw_latch, guess,
buf_mode, file, line, mtr);
tree_blocks[n_blocks] = block;
/* Search for complete index fields. */
up_bytes = low_bytes = 0;
// 对 page 内部的 record list 进行二分搜索 (page_cur_search_with_match)
// page_cur_search_with_match:在一个数据页内“二分查找”(使用数据页中的 directory slot),定位到 record
page_cur_search_with_match(
block, index, tuple, page_mode, &up_match,
&low_match, page_cursor,
need_path ? cursor->rtr_info : NULL);
其中:
/* Perform binary search until the lower and upper limit directory
slots come to the distance 1 of each other */
// 在索引页内查找对于指定的 tuple,满足某种条件(依赖于传入的 mode,比如 PAGE_CUR_L)的 record
// PAGE_CUR_G(>),PAGE_CUR_GE(>=),PAGE_CUR_L(index;
// btr_cur_t->page_cursor
page_cursor = btr_cur_get_page_cur(cursor);
/* Check locks and write to the undo log, if specified */
// 真正插入 entry 前,会检查事务锁和记录 undo
// 其中修改 inherit 值,如果下一条记录上没有锁,就不需要锁分裂
err = btr_cur_ins_lock_and_undo(flags, cursor, entry,
thr, mtr, &inherit);
if (err != DB_SUCCESS) {
goto fail_err;
}
// 插入数据
*rec = page_cur_tuple_insert(
page_cursor, entry, index, offsets, heap,
n_ext, mtr);
其中:
page_cur_tuple_insert 函数中调用 rec_convert_dtuple_to_rec_new 函数将逻辑记录转换成物理记录。
/*********************************************************//**
Builds a new-style physical record out of a data tuple and
stores it beginning from the start of the given buffer.
@return pointer to the origin of physical record */
static
rec_t*
rec_convert_dtuple_to_rec_new(
/*==========================*/
byte* buf, /*!< in: start address of the physical record */
const dict_index_t* index, /*!< in: record descriptor */
const dtuple_t* dtuple) /*!fields, dtuple->n_fields, &extra_size);
// 因为 buf 是用来存储整个记录的开始位置的,这里的 buf + extra_size 表示存储的第一个列的位置,即 rec 所指的位置
rec = buf + extra_size;
// 真正转换格式
rec_convert_dtuple_to_rec_comp(
rec, index, dtuple->fields, dtuple->n_fields, NULL,
status, false);
}
其中:
rec_convert_dtuple_to_rec_comp 函数中将每个列的值,以及 null 和 len 的信息存储到对应的位置。
/* Store the data and the offsets */
// 将每个列的值,以及 null 和 len 的信息存储到对应的位置
for (i = 0; i < n_fields; i++) {
const dict_field_t* ifield;
dict_col_t* col = NULL;
// 获取每个 field 的值
field = &fields[i];
// 计算 null 信息,因为这个标志是通过位来存储的,所以对每一个字节都需要做位处理
// 计算列的大小和存储其长度字节数动态匹配的位置,比如判断变长列的长度占用1个字节或2个字节
// 将元组列信息,写入到 compact 记录的对应列中,len为其对应的存储长度
memcpy(end, dfield_get_data(field), len);
}
最终调用 page_cur_insert_rec_low 函数将物理记录写入文件。
// 真正插入记录
rec = page_cur_insert_rec_low(cursor->rec,
index, rec, *offsets, mtr);
到这里就完成了一条数据的插入。
insert 过程中用到了多个数据结构进行数据的传递。
其中:
insert 过程中行记录格式发生了多次转换。
其中:
插入流程的具体函数堆栈可以参考文章【InnoDB –insert 操作分析】。
插入流程可以简化为下图。
其中:
MySQL 中有行格式有三种存储方式,包括 Server 层的格式、索引元组格式(逻辑记录,tuple)、物理存储记录格式(record)。
类似的,数据页分为两种形式,包括物理页(block)、内存页(page)。
通过 B+ 树索引进行查找(lookup)是最为常见的操作,具体通过游标实现。游标分为三种类型,包括 B-tree cursor、page cursor、persistent cursor。
存取数据时需要进行行格式的转换,原因是 IO 时使用二进制,内存操作时使用逻辑记录。
以插入数据为例,主要流程为:
其中数据格式的转换包括:
数据格式转换过程中涉及较多数据结构,其中:
如果您发现该资源为电子书等存在侵权的资源或对该资源描述不正确等,可点击“私信”按钮向作者进行反馈;如作者无回复可进行平台仲裁,我们会在第一时间进行处理!
加入交流群
请使用微信扫一扫!