1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
| /**
* B+树索引的核心数据结构和操作接口
* InnoDB中所有数据都存储在B+树结构中
*/
// B+树页面类型定义
enum page_type_t {
FIL_PAGE_INDEX = 17855, ///< B+树叶子页面
FIL_PAGE_RTREE = 17854, ///< R树页面（空间索引）
FIL_PAGE_SDI = 17853, ///< 序列化数据字典页面
FIL_PAGE_TYPE_ALLOCATED = 0, ///< 新分配的页面
FIL_PAGE_UNDO_LOG = 2, ///< Undo日志页面
FIL_PAGE_INODE = 3, ///< 段信息节点页面
FIL_PAGE_IBUF_FREE_LIST = 4, ///< 插入缓冲空闲列表页面
FIL_PAGE_TYPE_SYS = 6, ///< 系统页面
FIL_PAGE_TYPE_TRX_SYS = 7, ///< 事务系统页面
FIL_PAGE_TYPE_FSP_HDR = 8, ///< 文件空间头页面
FIL_PAGE_TYPE_XDES = 9, ///< 扩展描述页面
FIL_PAGE_TYPE_BLOB = 10, ///< BLOB页面
FIL_PAGE_TYPE_ZBLOB = 11, ///< 压缩BLOB页面
FIL_PAGE_TYPE_ZBLOB2 = 12 ///< 压缩BLOB页面(新格式)
};
/**
* B+树索引页面头部结构
* 包含页面的元数据信息
*/
struct page_header_t {
// 页面通用头部（38字节）
uint32_t checksum; ///< 页面校验和
uint32_t page_no; ///< 页面编号
uint32_t prev_page; ///< 前一页面编号
uint32_t next_page; ///< 后一页面编号
uint64_t lsn; ///< 页面LSN（日志序列号）
uint16_t page_type; ///< 页面类型
uint64_t file_flush_lsn; ///< 文件刷新LSN
uint32_t space_id; ///< 表空间ID
// 索引页面专用头部（36字节）
uint16_t n_dir_slots; ///< 页目录槽数量
uint16_t heap_top; ///< 堆顶位置（空闲空间开始）
uint16_t n_heap; ///< 页面中记录数（包括伪记录）
uint16_t free; ///< 指向第一个空闲记录
uint16_t garbage; ///< 被删除记录占用的字节数
uint16_t last_insert; ///< 最后插入记录的位置
uint16_t direction; ///< 插入方向（PAGE_LEFT, PAGE_RIGHT等）
uint16_t n_direction; ///< 同一方向连续插入的记录数
uint16_t n_recs; ///< 用户记录数量
uint64_t max_trx_id; ///< 修改页面的最大事务ID
uint16_t level; ///< B+树层级（0表示叶子层）
uint64_t index_id; ///< 索引ID
};
/**
* B+树记录格式结构
* InnoDB支持多种记录格式：Redundant、Compact、Dynamic、Compressed
*/
struct record_header_t {
// Compact格式记录头（5字节）
uint8_t info_flags; ///< 记录信息标志
uint16_t n_owned; ///< 拥有的记录数（仅目录记录使用）
uint16_t heap_no; ///< 堆中的位置编号
uint8_t record_type; ///< 记录类型（0=普通，1=B+树节点指针，2=最小记录，3=最大记录）
uint16_t next_record; ///< 指向下一条记录的偏移量
};
/**
* B+树游标结构
* 用于在B+树中定位和操作记录
*/
class btr_cur_t {
public:
// B+树路径信息
struct btr_path_t {
page_no_t page_no; ///< 页面编号
uint16_t nth_rec; ///< 页面中的记录序号
} path_arr[BTR_MAX_LEVELS]; ///< 从根到叶的路径数组
dict_index_t* index; ///< 索引对象指针
page_cur_t page_cur; ///< 页面游标
purge_node_t* purge_node; ///< 清理节点
buf_block_t* left_block; ///< 左兄弟页面块
que_thr_t* thr; ///< 查询线程
// 用于乐观插入和更新的成员
uint16_t flag; ///< BTR_CUR_DELETE_MARK等标志
ulint tree_height; ///< B+树高度
ulint up_match; ///< 向上匹配的记录数
ulint up_bytes; ///< 向上匹配的字节数
ulint low_match; ///< 向下匹配的记录数
ulint low_bytes; ///< 向下匹配的字节数
public:
/**
* 构造函数：初始化B+树游标
*/
btr_cur_t() : index(nullptr), purge_node(nullptr),
left_block(nullptr), thr(nullptr),
flag(0), tree_height(0), up_match(0),
up_bytes(0), low_match(0), low_bytes(0) {}
/**
* 在B+树中搜索记录
* @param tuple 搜索键值
* @param mode 搜索模式
* @param latch_mode 锁定模式
* @param cursor 游标对象
* @param mtr 迷你事务
* @return 搜索结果状态
*/
dberr_t search_to_nth_level(const dtuple_t* tuple,
page_cur_mode_t mode,
ulint latch_mode,
mtr_t* mtr) {
// 1. 从根页面开始搜索
dict_index_t* index = this->index;
buf_block_t* block = nullptr;
page_t* page = nullptr;
// 获取根页面
page_no_t root_page_no = dict_index_get_page(index);
space_id_t space_id = dict_index_get_space(index);
block = buf_page_get(page_id_t(space_id, root_page_no),
dict_table_page_size(index->table),
latch_mode, mtr);
page = buf_block_get_frame(block);
// 2. 逐层向下搜索
uint32_t level = btr_page_get_level(page, mtr);
while (level > 0) {
// 在非叶子页面中搜索
page_cur_search_with_match(block, index, tuple, mode,
&up_match, &up_bytes,
&low_match, &low_bytes,
&page_cur);
// 获取子页面页号
const rec_t* node_ptr = page_cur_get_rec(&page_cur);
page_no_t child_page_no = btr_node_ptr_get_child_page_no(node_ptr,
dict_index_get_n_unique_in_tree(index));
// 记录路径信息
path_arr[tree_height].page_no = page_get_page_no(page);
path_arr[tree_height].nth_rec = page_rec_get_n_recs_before(node_ptr);
tree_height++;
// 移动到子页面
block = buf_page_get(page_id_t(space_id, child_page_no),
dict_table_page_size(index->table),
latch_mode, mtr);
page = buf_block_get_frame(block);
level = btr_page_get_level(page, mtr);
}
// 3. 在叶子页面中精确搜索
page_cur_search_with_match(block, index, tuple, mode,
&up_match, &up_bytes,
&low_match, &low_bytes,
&page_cur);
return DB_SUCCESS;
}
/**
* 插入记录到B+树
* @param tuple 要插入的记录
* @param n_ext 外部存储字段数
* @param mtr 迷你事务
* @return 插入结果
*/
dberr_t optimistic_insert(const dtuple_t* tuple,
ulint n_ext,
mtr_t* mtr) {
page_t* page = page_cur_get_page(&page_cur);
dict_index_t* index = this->index;
// 1. 检查页面是否有足够空间
ulint rec_size = rec_get_converted_size(index, tuple, n_ext);
ulint max_size = page_get_max_insert_size_after_reorganize(page, 1);
if (rec_size > max_size) {
return DB_FAIL; // 需要页面分裂，转为悲观插入
}
// 2. 检查是否违反唯一性约束
if (dict_index_is_unique(index)) {
if (row_ins_duplicate_error_in_clust(this, tuple, mtr)) {
return DB_DUPLICATE_KEY;
}
}
// 3. 执行插入操作
rec_t* rec = page_cur_tuple_insert(&page_cur, tuple, index,
n_ext, mtr);
if (rec == nullptr) {
return DB_FAIL;
}
// 4. 更新页面统计信息
btr_search_update_hash_on_insert(this);
return DB_SUCCESS;
}
/**
* 删除当前记录
* @param mtr 迷你事务
* @return 删除结果
*/
dberr_t optimistic_delete(mtr_t* mtr) {
buf_block_t* block = page_cur_get_block(&page_cur);
page_t* page = buf_block_get_frame(block);
// 1. 检查页面合并条件
if (page_get_n_recs(page) < 2) {
return DB_FAIL; // 需要页面合并，转为悲观删除
}
// 2. 执行删除标记
page_cur_delete_rec(&page_cur, index, mtr);
// 3. 更新自适应哈希索引
btr_search_update_hash_on_delete(this);
return DB_SUCCESS;
}
};
/**
* B+树分裂操作
* 当页面空间不足时，需要进行页面分裂
*/
class btr_page_split_t {
private:
dict_index_t* index; ///< 索引对象
buf_block_t* block; ///< 要分裂的页面
const rec_t* split_rec; ///< 分裂点记录
public:
/**
* 执行页面分裂
* @param cursor B+树游标
* @param tuple 触发分裂的记录
* @param mtr 迷你事务
* @return 分裂结果
*/
dberr_t execute_split(btr_cur_t* cursor,
const dtuple_t* tuple,
mtr_t* mtr) {
// 1. 选择分裂点
const rec_t* split_rec = choose_split_point(cursor, tuple);
if (split_rec == nullptr) {
return DB_CORRUPTION;
}
// 2. 分配新页面
buf_block_t* new_block = btr_page_alloc(index, 0, FSP_UP,
btr_page_get_level(page, mtr),
mtr);
if (new_block == nullptr) {
return DB_OUT_OF_FILE_SPACE;
}
// 3. 创建新页面
page_t* new_page = buf_block_get_frame(new_block);
btr_page_create(new_block, index,
btr_page_get_level(page, mtr), mtr);
// 4. 移动记录到新页面
move_records_to_new_page(split_rec, new_block, mtr);
// 5. 更新页面链接
update_page_links(new_block, mtr);
// 6. 插入节点指针到父页面
insert_node_pointer_to_parent(cursor, new_block, mtr);
return DB_SUCCESS;
}
private:
/**
* 选择最优分裂点
* 目标是使两个页面的空间利用率尽可能平衡
*/
const rec_t* choose_split_point(btr_cur_t* cursor, const dtuple_t* tuple) {
page_t* page = page_cur_get_page(&cursor->page_cur);
// 获取页面中间位置的记录
ulint total_recs = page_get_n_recs(page);
ulint split_point = total_recs / 2;
const rec_t* rec = page_get_infimum_rec(page);
for (ulint i = 0; i < split_point; i++) {
rec = page_rec_get_next_const(rec);
if (page_rec_is_supremum(rec)) {
break;
}
}
return rec;
}
/**
* 移动记录到新页面
*/
void move_records_to_new_page(const rec_t* split_rec,
buf_block_t* new_block,
mtr_t* mtr) {
page_t* page = buf_block_get_frame(block);
page_t* new_page = buf_block_get_frame(new_block);
// 从分裂点开始，将后续记录移动到新页面
const rec_t* rec = split_rec;
while (!page_rec_is_supremum(rec)) {
const rec_t* next_rec = page_rec_get_next_const(rec);
// 复制记录到新页面
rec_t* new_rec = page_cur_insert_rec_low(
page_get_supremum_rec(new_page),
index, rec, mtr);
// 从原页面删除记录
page_delete_rec(page, rec, index, mtr);
rec = next_rec;
}
}
/**
* 更新页面链接关系
*/
void update_page_links(buf_block_t* new_block, mtr_t* mtr) {
page_t* page = buf_block_get_frame(block);
page_t* new_page = buf_block_get_frame(new_block);
// 获取原页面的下一页
page_no_t next_page_no = btr_page_get_next(page, mtr);
// 设置新页面的前后链接
btr_page_set_prev(new_page, page_get_page_no(page), mtr);
btr_page_set_next(new_page, next_page_no, mtr);
// 更新原页面的后继
btr_page_set_next(page, page_get_page_no(new_page), mtr);
// 更新下一页面的前驱（如果存在）
if (next_page_no != FIL_NULL) {
buf_block_t* next_block = buf_page_get(
page_id_t(index->space, next_page_no),
dict_table_page_size(index->table),
RW_X_LATCH, mtr);
page_t* next_page = buf_block_get_frame(next_block);
btr_page_set_prev(next_page, page_get_page_no(new_page), mtr);
}
}
};
|