引言
本文在介紹 MySQL 內存中記錄、頁、索引、游標的數據結構的基礎上，通過簡單分析插入操作過程中行格式的轉換介紹了不同數據結構的關系，其中不涉及加鎖相關邏輯。
原理
記錄
概念
InnoDB 存儲引擎基于記錄（record）存儲，表明記錄是根據行（row）格式存儲。
MySQL 中有行格式有以下三種存儲方式：
- Server 層的格式，這種格式與存儲引擎沒關系，適用于所有存儲引擎，這種格式是操作數據必然要經過的一種格式，也是 Row 模式下 binlog 存儲所使用的一種格式；
- 索引元組格式，這種格式是 InnoDB 存儲引擎在存取記錄時一種記錄格式的中間狀態(tài)，它要么是從 Server 層轉換而來，要是么轉換為 Server 層的格式。索引元組格式與索引一一對應，是內存中一種用來存儲索引中所有列數據的數據結構，對應邏輯記錄（tuple）；
- 物理存儲記錄格式，這種格式是一條記錄在物理頁面中的存儲格式，也就是 Compact 格式。這種格式與索引元組格式一一對應，對應物理記錄（record）。
因此：
- 存數據時，發(fā)生以下轉換：Server 層的格式 -> 索引元組格式 -> 物理存儲記錄格式；
- 取數據時，發(fā)生以下轉換：物理存儲記錄格式 -> 索引元組格式 -> Server 層的格式。
個人理解存取數據時完成二進制到“字符串”的相互轉換（忽略其他數據類型），相當于客戶端與服務端交互時的編碼與解碼。
數據結構
內存中邏輯記錄與其中的字段分別對應數據結構 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 */
};
其中：
- ulint n_fields，表示列的數量；
- dfield_t* fields，表示記錄中的列，存儲指向每一列真實數據的指針；
- UT_LIST_NODE_T(dtuple_t) tuple_list，連接多個 dtuple_t，原因是每個索引對應一個 dtuple_t，比如 INSERT SQL 需要向主鍵索引和二級索引中都插入時。
數據結構 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 */
};
其中：
- data，表示真實列數據的指針；
- ext:1，如果是大記錄（blob），則在外部頁存儲；
- len，表示列數據的長度；
- type，表示列數據的類型。
物理記錄由 rec_t 數據結構表示，字節(jié)類型。
/* We define the physical record simply as an array of bytes */
typedef byte rec_t;
頁
概念
頁和記錄類似同樣可以分為以下兩種形式：
- 物理頁（block），表示存儲在外部存儲設備上，一般是持久的。block 是文件系統中一次 IO 的大小；
- 內存頁（page），表示存儲在緩沖池（buffer pool）中，當物理頁與內存頁不同時表明是臟頁。
頁分多種類型，比如 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 information; this must
be the first field, so that
buf_pool->page_hash can point
to buf_page_t or buf_block_t */
byte* frame;
BPageLock lock; /*!< read-write lock of the buffer frame */
其中：
- block->buf_page_t，數據頁控制塊指針，要求是 buf_block_t 的第一個成員，便于 buf_block_t 隨時強制類型轉換為 buf_page_t；
- block->frame，數據頁指針，指向頁對應在緩沖池中的內存地址，保存頁的真實內容；
- block->lock，讀寫鎖用于保護 page 的內容。
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; /*!< node used in chAIning to
buf_pool->page_hash or
buf_pool->zip_hash */
lsn_t newest_modification; // 當前Page最新修改lsn
lsn_t oldest_modification; // 當前Page最老修改lsn，即第一條修改lsn
};
其中：
- oldest_modification，最初修改該頁 redo log record 的 end LSN（或者是 mtr end LSN），oldest_modification 不為 0 表示是臟頁；
- newest_modification，最近修改該頁 redo log record 的 end LSN（或者是 mtr end 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 */
};
其中：
- index->table，指向當前索引對應的表；
- index->n_fields，表示當前索引中包含的列數；
- index->page，表示當前索引 root 頁的編號（偏移量）；
- index->fields，表示當前索引列的描述信息。
通過 B+ 樹索引進行查找（lookup）是最為常見的操作，具體通過游標實現。
游標
概念
游標是一個邏輯概念，無論是寫入還是查詢，都需要在 B+ 樹上遍歷至某個位置，具體到某個 block 上的某個 record。
InnoDB 中通過 cursor search 實現 B+ 樹的查找，每個 open 一個 cursor 都會開啟一個從 B+ 樹 root 結點搜索到指定層級的 record 的搜索過程。
cursor 分為以下兩種：
- B-tree cursor
- page cursor，表示指向記錄所在位置的游標。
page cursor 在定位（lookup）到記錄后，再通過查詢模式（search mode）再進行向前或向后的記錄掃描（scan）。
比如對于一個主鍵的范圍查詢，首先需要定位第一條記錄，然后進行記錄的順序掃描。
InnoDB 中定義了四種查詢模式：
- PAGE_CUR_G: > 查詢，查詢第一個大于 dtuple 的 rec_t
- PAGE_CUR_GE: >=，> 查詢，查詢第一個大于等于 dtuple 的 rec_t
- PAGE_CUR_L: < 查詢，查詢最后一個小于 dtuple 的 rec_t
- PAGE_CUR_LE: <= 查詢，查詢最后一個小于等于 dtuple 的 rec_t
插入操作的 search_mode 默認是 PAGE_CUR_LE，即插在最后一個小于等于該 dtuple 的 rec_t 后。
為了提高查詢效率，InnoDB 做了以下優(yōu)化：
- record buffer，也就是預讀，連續(xù)讀取多條記錄；
- persistent cursor（持久化游標，簡稱 pcur），用于保存每次查詢到的記錄，待查詢下一條記錄時，首先恢復上一次查詢的記錄，然后再獲取下一條記錄；
- Adaptive Hash Index（自適應哈希索引，簡稱 AHI），根據熱點行記錄進行索引，但是如果記錄發(fā)生變化，也需要維護自適應哈希索引。
數據結構
B-tree cursor 對應 btr_cur_t 結構體。
/** The tree cursor: the definition Appears here only for the compiler
to know struct size! */
struct btr_cur_t {
btr_cur_t() { memset(this, 0, sizeof(*this)); }
dict_index_t* index; /*!< index where positioned */
page_cur_t page_cur; /*!< page cursor */
purge_node_t* purge_node; /*!< purge node, for BTR_DELETE */
buf_block_t* left_block; /*!< this field is used to store
a pointer to the left neighbor
page, in the cases
BTR_SEARCH_PREV and
BTR_MODIFY_PREV */
/*------------------------------*/
que_thr_t* thr; /*!< this field is only used
when btr_cur_search_to_nth_level
is called for an index entry
insertion: the calling query
thread is passed here to be
used in the insert buffer */
/*------------------------------*/
};
其中：
- page_cur_t page_cur，保存 page cursor 。
page cursor 對應 page_cur_t 結構體。
/** Index page cursor */
struct page_cur_t{
const dict_index_t* index;
rec_t* rec; /*!< pointer to a record on page */
ulint* offsets;
buf_block_t* block; /*!< pointer to the block containing rec */
};
其中：
- rec_t* rec，表示游標查詢得到的記錄；
- buf_block_t* block，表示表示游標查詢得到的記錄所在塊信息。
persistent cursor 對應 btr_pcur_t 數據結構。
/* The persistent B-tree cursor structure. This is used mainly for SQL
selects, updates, and deletes. */
struct btr_pcur_t{
btr_pcur_t() { memset(this, 0, sizeof(*this)); }
/** a B-tree cursor */
btr_cur_t btr_cur;
rec_t* old_rec;
/** Return the index of this persistent cursor */
dict_index_t* index() const { return(btr_cur.index); }
};
其中：
- rec_t* old_rec，持久化游標中保存查詢得到的記錄。
下面以 insert 語句的執(zhí)行為例，分析不同數據結構之間的關系。
insert 語句
build_template
從 server 層調用存儲引擎的接口 handler 開始，具體是 ha_innobase::write_row 函數。
// storage/innbase/handler/ha_innodb.cc
/* Stores a row in an InnoDB database, to the table specified in this handle. */
int
ha_innobase::write_row(
/*===================*/
uchar* record) /*!< in: a row in MySQL format */
{
/* Step-4: Prepare INSERT graph that will be executed for actual INSERT
(This is a one time operation) */
if (m_prebuilt->mysql_template == NULL
|| m_prebuilt->template_type != ROW_MYSQL_WHOLE_ROW) {
/* 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);
}
其中：
- 入參 uchar* record 指向 table->record[0]，其中不包含表列的類型、列的長度、列數等信息，完全是客戶端插入的數據；
unsigned char 數據類型經常被用于處理原始字節(jié)數據，比如在進行二進制文件讀寫、網絡通信、處理圖像數據、編碼轉換或者其他需要以字節(jié)為單位操作的場景中。利用 unsigned char 可以確保不會有負值出現，這在與二進制數據和位操作打交道時非常有用。
- 調用 build_template 函數初始化 m_prebuilt 變量；
- 調用 row_insert_for_mysql 函數插入數據，入參中將 record 指針從 uchar 轉換成 byte 類型。
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 */
};
其中：
- ins_node_t* ins_node，該結構體很重要，下文中將介紹；
- btr_pcur_t* pcur，持久化游標用于保存當前查詢的記錄；
- mysql_row_templ_t* mysql_template，輔助結構，主要保存列的元數據信息，用于加快行記錄格式的轉換。
row_prebuilt_t 結構體與 build_template 函數的作用參考 ChatGPT：
- row_prebuilt_t:row_prebuilt_t結構體是 InnoDB 存儲引擎用來預存儲有關某個表操作所需的信息的數據結構。這個結構體包括了眾多和查詢執(zhí)行相關的字段，如指向 InnoDB 內部諸如表描述（dict_table_t）、索引描述（dict_index_t）的指針；控制當前操作的游標狀態(tài)；查詢的模板信息；用于讀寫操作的緩沖區(qū)；鎖定信息等。簡言之，row_prebuilt_t是一個操作上下文，它保存了InnoDB在執(zhí)行諸如插入、更新、刪除、查詢等操作時所需要的所有上下文信息。
- build_template:build_template函數的主要工作是為 SQL 語句的執(zhí)行準備模板數據，這些數據用于確定當從存儲引擎獲取數據時應該返回哪些列，以及如何快速地從 InnoDB 的內部格式轉換為 MySQL 格式。例如，如果一個 SELECT 語句只查詢了表中的一些列，則build_template將生成相應的模板以確保只有這些被查詢的列的數據被讀取和轉換。這個過程包括決定哪些列可以跳過、哪些列需要轉換等。這樣就可以避免不必要的數據轉換和傳輸，提高查詢效率。
在 InnoDB 存儲引擎的設計中，row_prebuilt_t和build_template都是實現 SQL 層與存儲引擎層之間高效數據交互的重要組成部分。一方面，row_prebuilt_t作為一個操作上下文，保存了完成某個表操作所需的所有信息；另一方面，build_template則通過預先構建模板來優(yōu)化數據列的讀取和轉換過程。
byte -> dtuple_t* row
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;
// 主要構造用于執(zhí)行插入操作的 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;
// 執(zhí)行插入操作，插入記錄到主鍵索引、二級索引（包含唯一索引、非唯一索引）
/*插入記錄*/
row_ins_step(thr);
}
其中：
- 調用 row_get_prebuilt_insert_row 函數給 m_prebuilt->ins_node 成員賦初值，如 dtuple_t；
- 調用 row_mysql_convert_row_to_innobase 函數轉換行記錄格式；
- 調用 row_ins_step 函數插入記錄，其中入參 que_thr_t* thr，thr->run_node = node = prebuilt->ins_node，具體 que_thr_t 結構體暫不介紹。
這里又出現了一個重要的結構體 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 */
}
其中：
- dtuple_t* row，其中保存完整的行數據；
- dtuple_t* entry，給每個 index 創(chuàng)建一個 dtuple_t，用于保存索引中的數據，比如二級索引中只需要保存索引列和主鍵列，因此可以理解為針對特定索引優(yōu)化后的列版本。
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 < prebuilt->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,
/*!< ulint comp, nonzero=compact format */
dict_table_is_comp(prebuilt->table));
}
其中：
- 調用 row_mysql_store_col_in_innobase_format 函數將列值保存在 dtuple_t::dfield_t 中。
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);
其中：
- 獲取 dtype、計算 col_len
- 調用 dfield_set_data 函數保存數據完成行記錄格式的轉換
/* 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) /*!< in: length or UNIV_SQL_NULL */
{
field->data = (void*) data;
field->ext = 0;
field->len = static_cast<unsigned int>(len);
}
其中：
- 向 dfield_t 結構體中保存字段數據、字段長度
到這里完整的行數據索引元組格式 dtuple_t* row dtuple_t 準備好了，但由于 InnoDB 是索引組織樹，因此還需要將數據保存到索引元組格式 dtuple_t* entry 中。
dtuple_t* row -> dtuple_t* entry
row_ins_step 函數中創(chuàng)建 ins_node_t 并調用 row_ins 函數。
// 創(chuàng)建 ins_node_t
node = static_cast<ins_node_t*>(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);
其中：
- 循環(huán)調用 row_ins_index_entry_step 函數插入記錄，其中入參 node 就是 row_mysql_convert_row_to_innobase 函數轉換后的 row_prebuilt_t->ins_node_t；
- 每次插入索引時更新 ins_node_t->index 與 ins_node_t->entry，因此行數據對應的所有索引復用同一個 ins_node_t 變量，其中 ins_node_t->row 保持不變。
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) /*!< in: query thread */
{
/*給索引項賦值*/
err = row_ins_index_entry_set_vals(node->index, node->entry, node->row);
/*插入索引項*/
err = row_ins_index_entry(node->index, node->entry, thr);
}
其中：
- 調用 row_ins_index_entry_set_vals 函數遍歷索引的每個字段并賦值，其中將 innobase format field 的值賦給對應的 index entry field。
/** 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 < n_fields + num_v; i++) {
dfield_t* field;
const dfield_t* row_field;
ulint len;
// 獲取 field
field = dtuple_get_nth_field(entry, i);
row_field = dtuple_get_nth_field(
row, ind_field->col->ind);
len = dfield_get_len(row_field);
// 寫入 field
dfield_set_data(field, dfield_get_data(row_field), len);
}
其中：
- 與 row 相同，循環(huán)調用 dfield_set_data 方法給索引 entry 中的每個字段 field 賦值。
到這里每個索引的數據也準備好了，但是還不知道數據插入的位置，理論上是插在最后一個小于等于該 dtuple 的 rec_t 后。
cursor
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, /*!< in: 0 or index->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)
/*!< in: if true, just do duplicate check
and return. don't execute actual insert. */
{
btr_pcur_t pcur;
btr_cur_t* cursor;
// offsets
ulint offsets_[REC_OFFS_NORMAL_SIZE];
ulint* offsets = offsets_;
/* Note that we use PAGE_CUR_LE as the search mode, because then
the function will return in both low_match and up_match of the
cursor sensible values */
// 插入操作的 search_mode 默認是 PAGE_CUR_LE，即插在最后一個小于等于該 dtuple 的 rec_t 后
// btr_pcur_open 函數內部調用 btr_cur_search_to_nth_level 函數
btr_pcur_open(index, entry, PAGE_CUR_LE, mode, &pcur, &mtr);
// 從 btr_pcur_t 中獲取 btr_cur_t（tree cursor）
cursor = btr_pcur_get_btr_cur(&pcur);
cursor->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);
}
其中：
- 入參中包括 dict_index_t* index 與 dtuple_t* entry，分別對應 ins_node_t->index 與 ins_node_t->entry，其中 entry 中保存索引的數據；
- 調用 btr_pcur_open 函數將 cursor 移動到索引上待插入的位置，也就是定位頁與行，注意入參 mode = PAGE_CUR_LE；
- 調用 btr_cur_optimistic_insert 函數樂觀插入。
btr_pcur_open 函數中調用 btr_cur_search_to_nth_level 函數用于自頂向下查找整個 B-tree。
page_cursor = btr_cur_get_page_cur(cursor);
// 初始的，獲得索引的根節(jié)點（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);
其中：
- 調用 buf_page_get_gen 函數根據 page no 獲取 page（block），如果 page 在 buffer poo 中就直接讀取，否則從文件讀取到 buffer pool 中；
- 調用 page_cur_search_with_match 函數在 page 內部首先通過 Page Directory 二分查找確定 slot，然后線性查找確定行 record，其中 mode = PAGE_CUR_LE 。
/* 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（<），PAGE_CUR_LE（<=）
// 1. 二分查找
// 在稀疏的 Page Directory 內使用二分查找
low = 0;
up = page_dir_get_n_slots(page) - 1;
/* Perform linear search until the upper and lower records come to
distance 1 of each other. */
// 二分查找結束后，low / up是臨近的兩個 slot，這兩個 slot 指向的 record 記為
// low_rec 和 up_rec，滿足：low_rec <= tuple <= up_rec，切記 tuple 為待插入的（邏輯）記錄
// 2. 線性查找，漸漸夾逼
// 在兩個相鄰的 directory 內，進行線性查找。線性查找的實現即不斷"增大 low"，"減小 up"
其中：
- 二分查找與線性查找過程中都需要比較大小，具體調用 cmp_dtuple_rec_with_match_low 函數比較物理記錄與邏輯記錄的大小。
// storage/innobase/rem/rem0cmp.cc
/** Compare a data tuple to a physical record.
@param[in] dtuple data tuple
@param[in] rec B-tree record
@param[in] offsets rec_get_offsets(rec)
@param[in] n_cmp number of fields to compare
@param[in,out] matched_fields number of completely matched fields
@return the comparison result of dtuple and rec
@retval 0 if dtuple is equal to rec
@retval negative if dtuple is less than rec
@retval positive if dtuple is greater than rec */
int
cmp_dtuple_rec_with_match_low(
const dtuple_t* dtuple,
const rec_t* rec,
const ulint* offsets,
ulint n_cmp,
ulint* matched_fields)
{
/* Match fields in a loop */
// 遍歷記錄的每個字段
for (; cur_field < n_cmp; cur_field++) {
// 獲取邏輯記錄
const dfield_t* dtuple_field
= dtuple_get_nth_field(dtuple, cur_field);
// 將邏輯記錄轉換為物理記錄
const byte* dtuple_b_ptr
= static_cast<const byte*>(
dfield_get_data(dtuple_field));
// 根據 offset 獲取物理記錄
rec_b_ptr = rec_get_nth_field(rec, offsets, cur_field,
&rec_f_len);
// 比較大小
ret = cmp_data(type->mtype, type->prtype,
dtuple_b_ptr, dtuple_f_len,
rec_b_ptr, rec_f_len);
if (ret) {
goto order_resolved;
}
}
}
其中：
- 入參中包括邏輯記錄 dtuple、物理記錄 rec、記錄每個 field 偏移量的數組 offsets；
- 出參表示大小關系；
- 函數內部遍歷記錄的每個字段，先將邏輯記錄轉換為物理記錄，然后與根據 offset 獲取到的物理記錄比較大小。
到這里就定位到了數據插入的位置，開始真正的數據插入。
dtuple_t* entry -> byte
調用 btr_cur_optimistic_insert 函數樂觀插入。
page_cur_t* page_cursor;
buf_block_t* block;
// 通過 cursor 獲取 block
block = btr_cur_get_block(cursor);
// buf_block_t::frame 中保存 page
page = buf_block_get_frame(block);
index = cursor->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);
其中：
- buf_block_t::frame 是記錄要插入的數據頁，page_cursor 是記錄要插入的位置；
- 插入數據前調用 btr_cur_ins_lock_and_undo 函數檢查是否有與插入意向鎖沖突的鎖、是否需要發(fā)生鎖分裂；
- 調用 page_cur_tuple_insert 函數插入數據，邏輯記錄保存在 entry 中。
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) /*!< in: data tuple */
{
ulint extra_size;
ulint status;
rec_t* rec;
// 計算記錄頭大小，記錄頭大小用 extra_size 表示
rec_get_converted_size_comp(
index, status, 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 函數將 tuple 邏輯記錄轉換成物理記錄。
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 信息，因為這個標志是通過位來存儲的，所以對每一個字節(jié)都需要做位處理
// 計算列的大小和存儲其長度字節(jié)數動態(tài)匹配的位置，比如判斷變長列的長度占用1個字節(jié)或2個字節(jié)
// 將元組列信息，寫入到 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 過程中用到了多個數據結構進行數據的傳遞。
其中：
- row_prebuilt_t結構體中保存有關某個表操作相關信息，其中包括ins_node_t；
- ins_node_t結構體中保存插入操作相關的相關信息，其中包括dtuple_t；
- dtuple_t結構體中保存邏輯記錄，也就是索引元組，其中包括dfield_t；
- dfield_t結構體中保存字段信息，dfield_t::data中保存真實列數據的指針；
- btr_pcur_t結構體中包括btr_cur_t；
- btr_cur_t結構體中包括page_cur_t；
- page_cur_t結構體中保存查詢得到的記錄 rec，其中包括buf_block_t；
- buf_block_t結構體中保存數據頁指針 frame，其中包括buf_page_t。
insert 過程中行記錄格式發(fā)生了多次轉換。
其中：
- 首先從 byte 轉換成 dtuple_t* row，其中保存完整的行數據；
- 然后將 dtuple_t* row 轉換成 dtuple_t* entry，其中保存每個索引的列數據；
- 最后將 dtuple_t* entry 轉換成 byte，用于寫入文件。
插入流程的具體函數堆棧可以參考文章【InnoDB --insert 操作分析】。
插入流程可以簡化為下圖。
其中：
- 首先進行數據行格式轉換
- 然后定位要插入的位置
- 最后進行插入操作
結論
MySQL 中有行格式有三種存儲方式，包括 Server 層的格式、索引元組格式（邏輯記錄，tuple）、物理存儲記錄格式（record）。
類似的，數據頁分為兩種形式，包括物理頁（block）、內存頁（page）。
通過 B+ 樹索引進行查找（lookup）是最為常見的操作，具體通過游標實現。游標分為三種類型，包括 B-tree cursor、page cursor、persistent cursor。
存取數據時需要進行行格式的轉換，原因是 IO 時使用二進制，內存操作時使用邏輯記錄。
以插入數據為例，主要流程為：
- 首先進行數據行格式轉換
- 然后定位要插入的位置，基于 cursor 實現
- 最后進行插入操作
其中數據格式的轉換包括：
- 首先從 byte 轉換成 dtuple_t* row，其中保存完整的行數據；
- 然后將 dtuple_t* row 轉換成 dtuple_t* entry，其中保存每個索引的列數據；
- 最后將 dtuple_t* entry 轉換成 byte，用于寫入文件。
數據格式轉換過程中涉及較多數據結構，其中：
- dtuple_t結構體中保存邏輯記錄，也就是索引元組，其中包括dfield_t；
- dfield_t結構體中保存字段信息，dfield_t::data中保存真實列數據的指針；
- page_cur_t結構體中保存查詢得到的記錄 rec，其中包括buf_block_t；
- buf_block_t結構體中保存數據頁指針 frame，其中包括buf_page_t。
待辦
- row format
- cursor
- block
參考教程
- 《MySQL 內核 InnoDB 存儲引擎》
- 《MySQL 運維內參》
- InnoDB --insert 操作分析
https://zhuanlan.zhihu.com/p/103933731
- InnoDB：B-tree index（1）
https://zhuanlan.zhihu.com/p/164705538
- InnoDB：B-tree index（2）
https://zhuanlan.zhihu.com/p/164728032
- InnoDB：Buffer Pool
https://zhuanlan.zhihu.com/p/270343437
- MySQL · 源碼分析 · 一條insert語句的執(zhí)行過程
- MySQL · 內核分析 · InnoDB主鍵約束和唯一約束的實現分析
http://mysql.taobao.org/monthly/2021/04/05/
