。

GreatSQL是MySQL的国产分支版本#xff0c;使用上与MySQL一致。

作者#xff1a;

前文回顾

译注#xff1a;csta…GreatSQL社区原创内容未经授权不得随意使用转载请联系小编并注明来源。

GreatSQL是MySQL的国产分支版本使用上与MySQL一致。

作者

花家舍文章来源GreatSQL社区原创

译注cstack在github维护了一个简单的、类似sqlite的数据库实现通过这个简单的项目可以很好的理解数据库是如何运行的。

本文是第十篇主要是实现B-tree中叶子节点分裂

Part

tree。

为了解决这个问题需要一些代码来实现分裂叶子节点。

在那之后需要创建一个内部节点使其成为两个新的叶子节点的父节点。

one-node

exit(EXIT_FAILURE);leaf_node_split_and_insert(cursor,

key,

(statement-row_to_insert);uint32_t

key_to_insert

简单的部分结束了。

以下是我们需要做的事情的描述出自SQLite

Database

翻译如果在叶子节点中已经没有空间我们需要将驻留在节点中的现有条目和新条目正在插入分成相等的两半低半部分和高半部分在高半部分中的键要严格大于低半部分中的键。

我们分配一个新的节点将高半部分的条目移到新的节点中。

void

leaf_node_split_and_insert(Cursor*

cursor,

get_unused_page_num(cursor-table-pager);void*

new_node

new_page_num);initialize_leaf_node(new_node);

/*All

LEAF_NODE_LEFT_SPLIT_COUNT;void*

destination

leaf_node_cell(destination_node,

cursor-cell_num)

*/*(leaf_node_num_cells(old_node))

LEAF_NODE_LEFT_SPLIT_COUNT;*(leaf_node_num_cells(new_node))

然后我们需要更新节点的父节点。

如果原始节点是一个根节点root

node那么他就没有父节点。

这种情况中创建一个新的根节点来作为它的父节点。

这里做另外一个存根先不具体实现

{return

让我们回过头来定义一些函数和常量。

当我们创建一个新的叶子节点我们把它放进一个由get_unused_page_num()函数决定(返回)的页中。

Until

N编码。

在我们最终实现删除数据操作后一些页可能会变成空页并且他们的页编号可能没有被使用。

为了更有效率我们会回收这些空闲页。

Node

为了保持的树的平衡我们在两个新的节点之间平等的分发单元格。

如果一个叶子节点可以hold住

个单元格那么在分裂期间我们需要分发

仍然是根节点。

注意这时树的深度已经增加了一层但是在没有违反任何

B-Tree

此时我们已经分配了右子节点并移动高半部分的条目到这个子节点。

我们的函数把这个右子节点作为输入并且分配一个新的页面来存放左子节点。

void

get_unused_page_num(table-pager);void*

left_child

旧的根节点已经被拷贝到左子节点所以我们可以重用根节点无需重新分配

Left

PAGE_SIZE);set_node_root(left_child,

false);

*/initialize_internal_node(root);set_node_root(root,

true);*internal_node_num_keys(root)

left_child_max_key

get_node_max_key(left_child);*internal_node_key(root,

left_child_max_key;*internal_node_right_child(root)

内部节点格式Internal

现在我们终于创建了内部节点我们就不得不定义它的布局了。

它从通用

header

的数量接下来是它右边子节点的页号。

内部节点的子节点指针始终比它的

key

INTERNAL_NODE_RIGHT_CHILD_OFFSET

const

INTERNAL_NODE_RIGHT_CHILD_SIZE;

body

注意我们巨大的分支因子也就是扇出。

因为每个子节点指针/键对儿child

pointer

个子指针也就是每个内部节点可以有510个子节点。

这意味着我们从来不用在查找

key

internal_node_right_child(void*

node)

INTERNAL_NODE_RIGHT_CHILD_OFFSET;

}uint32_t*

*internal_node_num_keys(node);if

(child_num

internal_node_right_child(node);}

else

false);*leaf_node_num_cells(node)

}void

NODE_INTERNAL);set_node_root(node,

false);*internal_node_num_keys(node)

is_root

initialize_leaf_node(root_node);set_node_root(root_node,

true);

实现一个递归函数可以接受任何节点然后打印它和它的子节点。

它接受一个缩进级别作为参数缩进级别每次在每次递归时会递增。

我还在缩进中添加了一个很小的辅助函数。

void

*leaf_node_num_cells(node);indent(indentation_level);printf(-

leaf

*internal_node_num_keys(node);indent(indentation_level);printf(-

internal

*internal_node_right_child(node);print_tree(pager,

child,

print_leaf_node(get_page(table-pager,

0);return

run_script(script)expect(result[14...(result.length)]).to

match_array([db

如果你一直密切关注你可能会注意到我们错过了一些大事。

看看如果我们尝试插入额外一行会发生什么

insert

GreatSQL是由万里数据库维护的MySQL分支专注于提升MGR可靠性及性能支持InnoDB并行查询特性是适用于金融级应用的MySQL分支版本。

相关链接

https://greatsql.cn/thread-54-1-1.html

社区博客有奖征稿详情

https://greatsql.cn/thread-100-1-1.html

社区2022年度勋章获奖名单

https://greatsql.cn/thread-184-1-1.html

技术交流群