精通网站建设 pdf,安徽东皖建设集团有限公司网站,wordpress 文章相册,个人注册公司需要哪些材料GreatSQL社区原创内容未经授权不得随意使用#xff0c;转载请联系小编并注明来源。GreatSQL是MySQL的国产分支版本#xff0c;使用上与MySQL一致。作者#xff1a; 花家舍文章来源#xff1a;GreatSQL社区原创
前文回顾
实现一个简单的Database系列 译注#xff1a;csta…GreatSQL社区原创内容未经授权不得随意使用转载请联系小编并注明来源。GreatSQL是MySQL的国产分支版本使用上与MySQL一致。作者 花家舍文章来源GreatSQL社区原创
前文回顾
实现一个简单的Database系列 译注cstack在github维护了一个简单的、类似sqlite的数据库实现通过这个简单的项目可以很好的理解数据库是如何运行的。本文是第十篇主要是实现B-tree中叶子节点分裂
Part 10 叶子节点分裂
我们 B-Tree 只有一个节点这看起来不太像一棵标准的 tree。为了解决这个问题需要一些代码来实现分裂叶子节点。在那之后需要创建一个内部节点使其成为两个新的叶子节点的父节点。
基本上我们这个系列的文章的目标是从这里开始的 one-node btree
到这样 two-level btree
首先中的首先先把处理节点写满错误移除掉
void leaf_node_insert(Cursor* cursor, uint32_t key, Row* value) {void* node get_page(cursor-table-pager, cursor-page_num);uint32_t num_cells *leaf_node_num_cells(node);if (num_cells LEAF_NODE_MAX_CELLS) {// Node full
- printf(Need to implement splitting a leaf node.\n);
- exit(EXIT_FAILURE);leaf_node_split_and_insert(cursor, key, value);return;}
ExecuteResult execute_insert(Statement* statement, Table* table) {void* node get_page(table-pager, table-root_page_num);uint32_t num_cells (*leaf_node_num_cells(node));
- if (num_cells LEAF_NODE_MAX_CELLS) {
- return EXECUTE_TABLE_FULL;
- }Row* row_to_insert (statement-row_to_insert);uint32_t key_to_insert row_to_insert-id;
分裂算法Splitting Algorithm
简单的部分结束了。以下是我们需要做的事情的描述出自SQLite Database System: Design and Implementation 原文If there is no space on the leaf node, we would split the existing entries residing there and the new one (being inserted) into two equal halves: lower and upper halves. (Keys on the upper half are strictly greater than those on the lower half.) We allocate a new leaf node, and move the upper half into the new node. 翻译如果在叶子节点中已经没有空间我们需要将驻留在节点中的现有条目和新条目正在插入分成相等的两半低半部分和高半部分在高半部分中的键要严格大于低半部分中的键。我们分配一个新的节点将高半部分的条目移到新的节点中。
现在来处理旧节点并创建一个新的节点
void leaf_node_split_and_insert(Cursor* cursor, uint32_t key, Row* value) {/*Create a new node and move half the cells over.Insert the new value in one of the two nodes.Update parent or create a new parent.*/void* old_node get_page(cursor-table-pager, cursor-page_num);uint32_t new_page_num get_unused_page_num(cursor-table-pager);void* new_node get_page(cursor-table-pager, new_page_num);initialize_leaf_node(new_node);
接下来拷贝节点中每一个单元格到新的位置 /*All existing keys plus new key should be dividedevenly between old (left) and new (right) nodes.Starting from the right, move each key to correct position.*/for (int32_t i LEAF_NODE_MAX_CELLS; i 0; i--) {void* destination_node;if (i LEAF_NODE_LEFT_SPLIT_COUNT) {destination_node new_node;} else {destination_node old_node;}uint32_t index_within_node i % LEAF_NODE_LEFT_SPLIT_COUNT;void* destination leaf_node_cell(destination_node, index_within_node);if (i cursor-cell_num) {serialize_row(value, destination);} else if (i cursor-cell_num) {memcpy(destination, leaf_node_cell(old_node, i - 1), LEAF_NODE_CELL_SIZE);} else {memcpy(destination, leaf_node_cell(old_node, i), LEAF_NODE_CELL_SIZE);}}
更新节点中头部标记的单元格的数量更新node’s header /* Update cell count on both leaf nodes */*(leaf_node_num_cells(old_node)) LEAF_NODE_LEFT_SPLIT_COUNT;*(leaf_node_num_cells(new_node)) LEAF_NODE_RIGHT_SPLIT_COUNT;
然后我们需要更新节点的父节点。如果原始节点是一个根节点root node那么他就没有父节点。这种情况中创建一个新的根节点来作为它的父节点。这里做另外一个存根先不具体实现 if (is_node_root(old_node)) {return create_new_root(cursor-table, new_page_num);} else {printf(Need to implement updating parent after split\n);exit(EXIT_FAILURE);}
}
分配新的页面Allocating New Pages
让我们回过头来定义一些函数和常量。当我们创建一个新的叶子节点我们把它放进一个由get_unused_page_num()函数决定(返回)的页中。
/*
Until we start recycling free pages, new pages will always
go onto the end of the database file
*/
uint32_t get_unused_page_num(Pager* pager) { return pager-num_pages; }
现在我们假定在一个数据库中有N个数据页页编码从 0 到 N-1 的页已经被分配。因此我们总是可以为一个新页分配页 N编码。在我们最终实现删除数据操作后一些页可能会变成空页并且他们的页编号可能没有被使用。为了更有效率我们会回收这些空闲页。
叶子节点的大小Leaf Node Sizes
为了保持的树的平衡我们在两个新的节点之间平等的分发单元格。如果一个叶子节点可以hold住 N 个单元格那么在分裂期间我们需要分发 N 1 个单元格在两个节点之间N 个原有的单元格和一个新插入的单元格。如果 N1 是奇数我比较随意地选择了左侧节点获取多的那个单元格。
const uint32_t LEAF_NODE_RIGHT_SPLIT_COUNT (LEAF_NODE_MAX_CELLS 1) / 2;
const uint32_t LEAF_NODE_LEFT_SPLIT_COUNT (LEAF_NODE_MAX_CELLS 1) - LEAF_NODE_RIGHT_SPLIT_COUNT;
创建新根节点Creating a New Root
这里是“SQLite Database System”描述的创建一个新根节点的过程 原文Let N be the root node. First allocate two nodes, say L and R. Move lower half of N into L and the upper half into R. Now N is empty. Add 〈L, K,R〉 in N, where K is the max key in L. Page N remains the root. Note that the depth of the tree has increased by one, but the new tree remains height balanced without violating any B-tree property. 翻译设 N 为根节点。先分配两个节点比如 L 和 R。移动 N 中低半部分的条目到 L 中移动高半部分条目到 R 中。现在 N 已经空了。增加 〈L, K,R〉到 N 中这里 K 是 L 中最大 key 。页 N 仍然是根节点。注意这时树的深度已经增加了一层但是在没有违反任何 B-Tree 属性的情况下新的树仍然保持了高度上平衡。
此时我们已经分配了右子节点并移动高半部分的条目到这个子节点。我们的函数把这个右子节点作为输入并且分配一个新的页面来存放左子节点。
void create_new_root(Table* table, uint32_t right_child_page_num) {/*Handle splitting the root.Old root copied to new page, becomes left child.Address of right child passed in.Re-initialize root page to contain the new root node.New root node points to two children.*/void* root get_page(table-pager, table-root_page_num);void* right_child get_page(table-pager, right_child_page_num);uint32_t left_child_page_num get_unused_page_num(table-pager);void* left_child get_page(table-pager, left_child_page_num);
旧的根节点已经被拷贝到左子节点所以我们可以重用根节点无需重新分配 /* Left child has data copied from old root */memcpy(left_child, root, PAGE_SIZE);set_node_root(left_child, false);
最后我们初始化根节点作为一个新的、有两个子节点的内部节点。 /* Root node is a new internal node with one key and two children */initialize_internal_node(root);set_node_root(root, true);*internal_node_num_keys(root) 1;*internal_node_child(root, 0) left_child_page_num;uint32_t left_child_max_key get_node_max_key(left_child);*internal_node_key(root, 0) left_child_max_key;*internal_node_right_child(root) right_child_page_num;
}
内部节点格式Internal Node Format
现在我们终于创建了内部节点我们就不得不定义它的布局了。它从通用 header 开始然后是它包含的 key 的数量接下来是它右边子节点的页号。内部节点的子节点指针始终比它的 key 的数量多一个。这个 子节点指针存储在 header 中。
/** Internal Node Header Layout*/
const uint32_t INTERNAL_NODE_NUM_KEYS_SIZE sizeof(uint32_t);
const uint32_t INTERNAL_NODE_NUM_KEYS_OFFSET COMMON_NODE_HEADER_SIZE;
const uint32_t INTERNAL_NODE_RIGHT_CHILD_SIZE sizeof(uint32_t);
const uint32_t INTERNAL_NODE_RIGHT_CHILD_OFFSET INTERNAL_NODE_NUM_KEYS_OFFSET INTERNAL_NODE_NUM_KEYS_SIZE;
const uint32_t INTERNAL_NODE_HEADER_SIZE COMMON_NODE_HEADER_SIZE INTERNAL_NODE_NUM_KEYS_SIZE INTERNAL_NODE_RIGHT_CHILD_SIZE;
内部节点的 body 是一个单元格的数组每个单元格包含一个子指针和一个 key 。每个 key 都必须是它的左边子节点中包含的最大 key 。
/** Internal Node Body Layout*/
const uint32_t INTERNAL_NODE_KEY_SIZE sizeof(uint32_t);
const uint32_t INTERNAL_NODE_CHILD_SIZE sizeof(uint32_t);
const uint32_t INTERNAL_NODE_CELL_SIZE INTERNAL_NODE_CHILD_SIZE INTERNAL_NODE_KEY_SIZE;
基于这些常量下边是内部节点布局看上去的样子 Our internal node format
注意我们巨大的分支因子也就是扇出。因为每个子节点指针/键对儿child pointer / key pair太小了我们可以在每个内部节点中容纳 510 个键和 511 个子指针也就是每个内部节点可以有510个子节点。这意味着我们从来不用在查找 key 时遍历树的很多层。
# internal node layersmax # leaf nodesSize of all leaf nodes0511^0 14 KB1511^1 512~2 MB2511^2 261,121~1 GB3511^3 133,432,831~550 GB
实际上我们不能在每个叶子节点中存储满 4KB 的数据这是因为存储 header 、 keys 的开销和空间的浪费。 但是我们可以通过从磁盘上加载 4 个 pages 树高四层每层只需检索一页来检索大约 500G 的数据。这就是为什么 B-Tree 对数据库来说是很有用的数据结构。
下边是读取和写入一个内部节点的方法
uint32_t* internal_node_num_keys(void* node) {return node INTERNAL_NODE_NUM_KEYS_OFFSET;
}uint32_t* internal_node_right_child(void* node) {return node INTERNAL_NODE_RIGHT_CHILD_OFFSET;
}uint32_t* internal_node_cell(void* node, uint32_t cell_num) {return node INTERNAL_NODE_HEADER_SIZE cell_num * INTERNAL_NODE_CELL_SIZE;
}uint32_t* internal_node_child(void* node, uint32_t child_num) {uint32_t num_keys *internal_node_num_keys(node);if (child_num num_keys) {printf(Tried to access child_num %d num_keys %d\n, child_num, num_keys);exit(EXIT_FAILURE);} else if (child_num num_keys) {return internal_node_right_child(node);} else {return internal_node_cell(node, child_num);}
}uint32_t* internal_node_key(void* node, uint32_t key_num) {return internal_node_cell(node, key_num) INTERNAL_NODE_CHILD_SIZE;
}
对于一个内部节点最大 key 始终是其右键。对于一个叶子节点最大 key 就是最大索引键。
uint32_t get_node_max_key(void* node) {switch (get_node_type(node)) {case NODE_INTERNAL:return *internal_node_key(node, *internal_node_num_keys(node) - 1);case NODE_LEAF:return *leaf_node_key(node, *leaf_node_num_cells(node) - 1);}
}
追踪根节点Keeping Track of the Root
我们终于在通用的节点 header 中使用了 is_root 字段。回调它是我们用它来决定怎样来分裂一个叶子节点 if (is_node_root(old_node)) {return create_new_root(cursor-table, new_page_num);} else {printf(Need to implement updating parent after split\n);exit(EXIT_FAILURE);}
}
下面是 getter setter
bool is_node_root(void* node) {uint8_t value *((uint8_t*)(node IS_ROOT_OFFSET));return (bool)value;
}void set_node_root(void* node, bool is_root) {uint8_t value is_root;*((uint8_t*)(node IS_ROOT_OFFSET)) value;
}
初始化这两种类型的节点内部节点叶子节点应默认设置 is_root 为 false。
void initialize_leaf_node(void* node) {set_node_type(node, NODE_LEAF);set_node_root(node, false);*leaf_node_num_cells(node) 0;
}void initialize_internal_node(void* node) {set_node_type(node, NODE_INTERNAL);set_node_root(node, false);*internal_node_num_keys(node) 0;
}
当创建表的第一个节点时我们需要设置 is_root 为 true 。
// New database file. Initialize page 0 as leaf node.
void* root_node get_page(pager, 0);
initialize_leaf_node(root_node);set_node_root(root_node, true);
}return table;
打印树Printing the Tree
为了帮助我们可视化数据库的状态我们应该更新我们的 .btree 元命令以打印多级树。
我要替换当前的 print_leaf_node 函数
-void print_leaf_node(void* node) {
- uint32_t num_cells *leaf_node_num_cells(node);
- printf(leaf (size %d)\n, num_cells);
- for (uint32_t i 0; i num_cells; i) {
- uint32_t key *leaf_node_key(node, i);
- printf( - %d : %d\n, i, key);
- }
-}
实现一个递归函数可以接受任何节点然后打印它和它的子节点。它接受一个缩进级别作为参数缩进级别每次在每次递归时会递增。我还在缩进中添加了一个很小的辅助函数。
void indent(uint32_t level) {for (uint32_t i 0; i level; i) {printf( );}
}void print_tree(Pager* pager, uint32_t page_num, uint32_t indentation_level) {void* node get_page(pager, page_num);uint32_t num_keys, child;switch (get_node_type(node)) {case (NODE_LEAF):num_keys *leaf_node_num_cells(node);indent(indentation_level);printf(- leaf (size %d)\n, num_keys);for (uint32_t i 0; i num_keys; i) {indent(indentation_level 1);printf(- %d\n, *leaf_node_key(node, i));}break;case (NODE_INTERNAL):num_keys *internal_node_num_keys(node);indent(indentation_level);printf(- internal (size %d)\n, num_keys);for (uint32_t i 0; i num_keys; i) {child *internal_node_child(node, i);print_tree(pager, child, indentation_level 1);indent(indentation_level 1);printf(- key %d\n, *internal_node_key(node, i));}child *internal_node_right_child(node);print_tree(pager, child, indentation_level 1);break;}
}
并更新对 print 函数的调用传递缩进级别为零。
} else if (strcmp(input_buffer-buffer, .btree) 0) {printf(Tree:\n);
- print_leaf_node(get_page(table-pager, 0));print_tree(table-pager, 0, 0);return META_COMMAND_SUCCESS;
下面是一个对新的打印函数的测例 it allows printing out the structure of a 3-leaf-node btree doscript (1..14).map do |i|insert #{i} user#{i} person#{i}example.comendscript .btreescript insert 15 user15 person15example.comscript .exitresult run_script(script)expect(result[14...(result.length)]).to match_array([db Tree:,- internal (size 1),- leaf (size 7),- 1,- 2,- 3,- 4,- 5,- 6,- 7,- key 7,- leaf (size 7),- 8,- 9,- 10,- 11,- 12,- 13,- 14,db Need to implement searching an internal node,])end
新格式有点简化所以我们需要更新现有的 .btree 测试
db Executed.,
db Executed.,
db Tree:,
- leaf (size 3),
- - 0 : 1,
- - 1 : 2,
- - 2 : 3,- leaf (size 3),- 1,- 2,- 3,
db
])
end
这是新测试本身的 .btree 输出
Tree:
- internal (size 1)- leaf (size 7)- 1- 2- 3- 4- 5- 6- 7- key 7- leaf (size 7)- 8- 9- 10- 11- 12- 13- 14
在缩进最小的级别我们看到根节点一个内部节点。它输出的 size 为 1 因为它有一个 key 。缩进一个级别我们看到叶子节点一个 key 和一个叶子节点。根节点中的 key 7是第一个左子节点中最大的 key 。每个大于7的 key 存放在第二个子节点中。
一个主要问题A Major Problem
如果你一直密切关注你可能会注意到我们错过了一些大事。看看如果我们尝试插入额外一行会发生什么
db insert 15 user15 person15example.com
Need to implement searching an internal node
哦吼是谁写的TODO信息作者在故弄玄虚明明是他自己在 table_find() 函数中把内部节点搜索的功能存根的
下次我们将通过在多级树上实现搜索来继续史诗般的 B 树传奇。
Enjoy GreatSQL :)
关于 GreatSQL
GreatSQL是由万里数据库维护的MySQL分支专注于提升MGR可靠性及性能支持InnoDB并行查询特性是适用于金融级应用的MySQL分支版本。
相关链接 GreatSQL社区 Gitee GitHub Bilibili
GreatSQL社区 社区有奖建议反馈 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
对文章有疑问或者有独到见解都可以去社区官网提出或分享哦~
技术交流群
微信QQ群 QQ群533341697 微信群添加GreatSQL社区助手微信号wanlidbc 好友待社区助手拉您进群。 文章转载自： http://www.morning.xhxsr.cn.gov.cn.xhxsr.cn http://www.morning.smygl.cn.gov.cn.smygl.cn http://www.morning.qcrhb.cn.gov.cn.qcrhb.cn http://www.morning.tbjb.cn.gov.cn.tbjb.cn http://www.morning.fkwp.cn.gov.cn.fkwp.cn http://www.morning.jbztm.cn.gov.cn.jbztm.cn http://www.morning.wklhn.cn.gov.cn.wklhn.cn http://www.morning.qckwj.cn.gov.cn.qckwj.cn http://www.morning.ngmjn.cn.gov.cn.ngmjn.cn http://www.morning.qphdp.cn.gov.cn.qphdp.cn http://www.morning.pwbps.cn.gov.cn.pwbps.cn http://www.morning.nzmqn.cn.gov.cn.nzmqn.cn http://www.morning.zpnfc.cn.gov.cn.zpnfc.cn http://www.morning.zbtfz.cn.gov.cn.zbtfz.cn http://www.morning.xlyt.cn.gov.cn.xlyt.cn http://www.morning.qjxkx.cn.gov.cn.qjxkx.cn http://www.morning.rbsmm.cn.gov.cn.rbsmm.cn http://www.morning.cbchz.cn.gov.cn.cbchz.cn http://www.morning.crtgd.cn.gov.cn.crtgd.cn http://www.morning.gbsby.cn.gov.cn.gbsby.cn http://www.morning.zjrnq.cn.gov.cn.zjrnq.cn http://www.morning.pqhfx.cn.gov.cn.pqhfx.cn http://www.morning.nhpmn.cn.gov.cn.nhpmn.cn http://www.morning.djwpd.cn.gov.cn.djwpd.cn http://www.morning.sfhjx.cn.gov.cn.sfhjx.cn http://www.morning.hwsgk.cn.gov.cn.hwsgk.cn http://www.morning.cplym.cn.gov.cn.cplym.cn http://www.morning.xfncq.cn.gov.cn.xfncq.cn http://www.morning.5-73.com.gov.cn.5-73.com http://www.morning.hhqjf.cn.gov.cn.hhqjf.cn http://www.morning.rwdbz.cn.gov.cn.rwdbz.cn http://www.morning.rczrq.cn.gov.cn.rczrq.cn http://www.morning.httzf.cn.gov.cn.httzf.cn http://www.morning.qznkn.cn.gov.cn.qznkn.cn http://www.morning.skqfx.cn.gov.cn.skqfx.cn http://www.morning.psgbk.cn.gov.cn.psgbk.cn http://www.morning.wckrl.cn.gov.cn.wckrl.cn http://www.morning.wwdlg.cn.gov.cn.wwdlg.cn http://www.morning.gtqx.cn.gov.cn.gtqx.cn http://www.morning.khzml.cn.gov.cn.khzml.cn http://www.morning.rjnx.cn.gov.cn.rjnx.cn http://www.morning.tdqhs.cn.gov.cn.tdqhs.cn http://www.morning.czxrg.cn.gov.cn.czxrg.cn http://www.morning.hnrdtz.com.gov.cn.hnrdtz.com http://www.morning.bbyqz.cn.gov.cn.bbyqz.cn http://www.morning.qieistand.com.gov.cn.qieistand.com http://www.morning.ykrkb.cn.gov.cn.ykrkb.cn http://www.morning.ssqrd.cn.gov.cn.ssqrd.cn http://www.morning.bfmrq.cn.gov.cn.bfmrq.cn http://www.morning.xrmwc.cn.gov.cn.xrmwc.cn http://www.morning.nykzl.cn.gov.cn.nykzl.cn http://www.morning.kryn.cn.gov.cn.kryn.cn http://www.morning.ntwxt.cn.gov.cn.ntwxt.cn http://www.morning.dyxlj.cn.gov.cn.dyxlj.cn http://www.morning.bpmnq.cn.gov.cn.bpmnq.cn http://www.morning.ztfzm.cn.gov.cn.ztfzm.cn http://www.morning.qjbxt.cn.gov.cn.qjbxt.cn http://www.morning.mqbsm.cn.gov.cn.mqbsm.cn http://www.morning.pzcjq.cn.gov.cn.pzcjq.cn http://www.morning.rknsp.cn.gov.cn.rknsp.cn http://www.morning.zfcfx.cn.gov.cn.zfcfx.cn http://www.morning.kbynw.cn.gov.cn.kbynw.cn http://www.morning.yqjjn.cn.gov.cn.yqjjn.cn http://www.morning.kmldm.cn.gov.cn.kmldm.cn http://www.morning.fhtbk.cn.gov.cn.fhtbk.cn http://www.morning.znrgq.cn.gov.cn.znrgq.cn http://www.morning.jrhcp.cn.gov.cn.jrhcp.cn http://www.morning.mttck.cn.gov.cn.mttck.cn http://www.morning.prgdy.cn.gov.cn.prgdy.cn http://www.morning.qtkfp.cn.gov.cn.qtkfp.cn http://www.morning.xjkr.cn.gov.cn.xjkr.cn http://www.morning.mhfbp.cn.gov.cn.mhfbp.cn http://www.morning.zdwjg.cn.gov.cn.zdwjg.cn http://www.morning.ndxss.cn.gov.cn.ndxss.cn http://www.morning.sqtsl.cn.gov.cn.sqtsl.cn http://www.morning.zkbxx.cn.gov.cn.zkbxx.cn http://www.morning.fwcnx.cn.gov.cn.fwcnx.cn http://www.morning.kdjtt.cn.gov.cn.kdjtt.cn http://www.morning.qnzk.cn.gov.cn.qnzk.cn http://www.morning.hxgly.cn.gov.cn.hxgly.cn
