/** 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 */
};

/** 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 */
};

/* We define the physical record simply as an array of bytes */
typedef byte rec_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 */

/** 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; // 當(dāng)前Page最新修改lsn
  lsn_t  oldest_modification; // 當(dāng)前Page最老修改lsn，即第一條修改lsn
  
};

/** 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 */
};

/** 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 */
 /*------------------------------*/

};

/** 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 */
};

/* 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); }
};

// 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. */
 // 插入數(shù)據(jù)
 error = row_insert_for_mysql((byte*) record, m_prebuilt);
}

typedef unsigned char uchar; /* Short for unsigned char */

/* Note that inside MySQL 'byte' is defined as char on Linux! */
#define byte   unsigned char

/** 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 */
};

// 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;
  
  // 主要構(gòu)造用于執(zhí)行插入操作的 2 個(gè)對(duì)象：
 // 1. ins_node_t 對(duì)象，保存在 prebuilt->ins_node 中
 // 2. que_fork_t 對(duì)象，保存在 prebuilt->ins_graph 中
 row_get_prebuilt_insert_row(prebuilt);
 node = prebuilt->ins_node;

 // 把 server 層的記錄格式轉(zhuǎn)換為 InnoDB 的記錄格式
 row_mysql_convert_row_to_innobase(node->row, prebuilt, mysql_rec,
       &blob_heap);
  
  thr->run_node = node;
 thr->prev_node = node;
  
  // 執(zhí)行插入操作，插入記錄到主鍵索引、二級(jí)索引（包含唯一索引、非唯一索引）
 /*插入記錄*/
 row_ins_step(thr);
}

/* 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 */
}

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);
    
    // 格式轉(zhuǎn)換，從 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));
}

const byte* ptr = mysql_data;
 const dtype_t* dtype;
 ulint  type;

 dtype = dfield_get_type(dfield);

 type = dtype->mtype;
  
  // 計(jì)算 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) /*!< in: length or UNIV_SQL_NULL */
{
 field->data = (void*) data;
 field->ext = 0;
 field->len = static_cast<unsigned int>(len);
}

// 創(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 */
 // 調(diào)用 row_ins() 插入記錄到主鍵索引、二級(jí)索引
 err = row_ins(node, thr);

// 遍歷所有索引，向每個(gè)索引中插入記錄
 while (node->index != NULL) {
    
    /* 向索引中插入記錄 */
    err = row_ins_index_entry_step(node, thr);

  // 插入記錄到主鍵索引或二級(jí)索引成功后獲取下一個(gè)索引
    // node->index、entry 指向表中的下一個(gè)索引
  node->index = dict_table_get_next_index(node->index);
  node->entry = UT_LIST_GET_NEXT(tuple_list, node->entry);

// 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 */
{
  /*給索引項(xiàng)賦值*/
 err = row_ins_index_entry_set_vals(node->index, node->entry, node->row);

 /*插入索引項(xiàng)*/
 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 < 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);
}

// 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 默認(rèn)是 PAGE_CUR_LE，即插在最后一個(gè)小于等于該 dtuple 的 rec_t 后
 // btr_pcur_open 函數(shù)內(nèi)部調(diào)用 btr_cur_search_to_nth_level 函數(shù)
 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;
  
  /* 樂(lè)觀插入 */
  err = btr_cur_optimistic_insert(
    flags, cursor, &offsets, &offsets_heap,
    entry, &insert_rec, &big_rec,
    n_ext, thr, &mtr);
}

page_cursor = btr_cur_get_page_cur(cursor);
 
 // 初始的，獲得索引的根節(jié)點(diǎn)（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（默認(rèn)是 4）
 page_id_t  page_id(space, dict_index_get_page(index));
  
  // 從 buffer_pool 中根據(jù) page no 拿 page（buf_page_get_gen），buffer pool 模塊會(huì)根據(jù) page 是否被緩存來(lái)決定是從內(nèi)存中還是磁盤中讀取，并根據(jù)加鎖策略對(duì) 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;
  // 對(duì) page 內(nèi)部的 record list 進(jìn)行二分搜索 (page_cur_search_with_match)
  // page_cur_search_with_match：在一個(gè)數(shù)據(jù)頁(yè)內(nèi)“二分查找”（使用數(shù)據(jù)頁(yè)中的 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 */
  
  // 在索引頁(yè)內(nèi)查找對(duì)于指定的 tuple，滿足某種條件（依賴于傳入的 mode，比如 PAGE_CUR_L）的 record
 // PAGE_CUR_G（>），PAGE_CUR_GE（>=），PAGE_CUR_L（<），PAGE_CUR_LE（<=）
 // 1. 二分查找
 // 在稀疏的 Page Directory 內(nèi)使用二分查找
 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. */

 // 二分查找結(jié)束后，low / up是臨近的兩個(gè) slot，這兩個(gè) slot 指向的 record 記為
  // low_rec 和 up_rec，滿足：low_rec <= tuple <= up_rec，切記 tuple 為待插入的（邏輯）記錄

  // 2. 線性查找，漸漸夾逼
  // 在兩個(gè)相鄰的 directory 內(nèi)，進(jìn)行線性查找。線性查找的實(shí)現(xiàn)即不斷"增大 low"，"減小 up"

// 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 */
  // 遍歷記錄的每個(gè)字段
 for (; cur_field < n_cmp; cur_field++) {
    
    // 獲取邏輯記錄
    const dfield_t* dtuple_field
   = dtuple_get_nth_field(dtuple, cur_field);
    
    // 將邏輯記錄轉(zhuǎn)換為物理記錄
    const byte* dtuple_b_ptr
   = static_cast<const byte*>(
    dfield_get_data(dtuple_field));
    
    // 根據(jù) 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;
  }
    
  }
}

page_cur_t* page_cursor;
 buf_block_t* block;
 
 // 通過(guò) 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 前，會(huì)檢查事務(wù)鎖和記錄 undo
  // 其中修改 inherit 值，如果下一條記錄上沒(méi)有鎖，就不需要鎖分裂
  err = btr_cur_ins_lock_and_undo(flags, cursor, entry,
          thr, mtr, &inherit);

  if (err != DB_SUCCESS) {
    goto fail_err;
  }

  // 插入數(shù)據(jù)
  *rec = page_cur_tuple_insert(
    page_cursor, entry, index, offsets, heap,
    n_ext, mtr);

/*********************************************************//**
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;

 // 計(jì)算記錄頭大小，記錄頭大小用 extra_size 表示
 rec_get_converted_size_comp(
  index, status, dtuple->fields, dtuple->n_fields, &extra_size);
 // 因?yàn)?buf 是用來(lái)存儲(chǔ)整個(gè)記錄的開(kāi)始位置的，這里的 buf + extra_size 表示存儲(chǔ)的第一個(gè)列的位置，即 rec 所指的位置
 rec = buf + extra_size;

 // 真正轉(zhuǎn)換格式
 rec_convert_dtuple_to_rec_comp(
  rec, index, dtuple->fields, dtuple->n_fields, NULL,
  status, false);
}

/* Store the data and the offsets */

 // 將每個(gè)列的值，以及 null 和 len 的信息存儲(chǔ)到對(duì)應(yīng)的位置
 for (i = 0; i < n_fields; i++) {
  const dict_field_t* ifield;
  dict_col_t*  col = NULL;
    
    // 獲取每個(gè) field 的值
  field = &fields[i];
    
    // 計(jì)算 null 信息，因?yàn)檫@個(gè)標(biāo)志是通過(guò)位來(lái)存儲(chǔ)的，所以對(duì)每一個(gè)字節(jié)都需要做位處理
    // 計(jì)算列的大小和存儲(chǔ)其長(zhǎng)度字節(jié)數(shù)動(dòng)態(tài)匹配的位置，比如判斷變長(zhǎng)列的長(zhǎng)度占用1個(gè)字節(jié)或2個(gè)字節(jié)
    
    // 將元組列信息，寫入到 compact 記錄的對(duì)應(yīng)列中，len為其對(duì)應(yīng)的存儲(chǔ)長(zhǎng)度
  memcpy(end, dfield_get_data(field), len);
  }

// 真正插入記錄
  rec = page_cur_insert_rec_low(cursor->rec,
              index, rec, *offsets, mtr);