实现一个简单的Database10(译文)

天卓数码

• GreatSQL社区原创内容未经授权不得随意使用，转载请联系小编并注明来源。
  
• GreatSQL是MySQL的国产分支版本，使用上与MySQL一致。
  
• 作者：  花家舍
  
• 文章来源：GreatSQL社区原创
  

前文回顾

• 实现一个简单的Database系列
  

译注：cstack在github维护了一个简单的、类似sqlite的数据库实现，通过这个简单的项目，可以很好的理解数据库是如何运行的。本文是第十篇，主要是实现B-tree中叶子节点分裂
Part 10 叶子节点分裂

我们 B-Tree 只有一个节点，这看起来不太像一棵标准的 tree。为了解决这个问题，需要一些代码来实现分裂叶子节点。在那之后，需要创建一个内部节点，使其成为两个新的叶子节点的父节点。
基本上，我们这个系列的文章的目标是从这里开始的：

one-node btree
到这样：

two-level btree
首先中的首先，先把处理节点写满错误移除掉：

1. void leaf_node_insert(Cursor* cursor, uint32_t key, Row* value) {
2.   void* node = get_page(cursor->table->pager, cursor->page_num);
4.   uint32_t num_cells = *leaf_node_num_cells(node);
5.   if (num_cells >= LEAF_NODE_MAX_CELLS) {
6.     // Node full
7. -    printf("Need to implement splitting a leaf node.\n");
8. -    exit(EXIT_FAILURE);
9. +    leaf_node_split_and_insert(cursor, key, value);
10. +    return;
11.   }
12. ExecuteResult execute_insert(Statement* statement, Table* table) {
13.    void* node = get_page(table->pager, table->root_page_num);
14.    uint32_t num_cells = (*leaf_node_num_cells(node));
15. -  if (num_cells >= LEAF_NODE_MAX_CELLS) {
16. -    return EXECUTE_TABLE_FULL;
17. -  }
19.    Row* row_to_insert = &(statement->row_to_insert);
20.    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.
翻译：如果在叶子节点中已经没有空间，我们需要将驻留在节点中的现有条目和新条目（正在插入）分成相等的两半：低半部分和高半部分（在高半部分中的键要严格大于低半部分中的键）。我们分配一个新的节点，将高半部分的条目移到新的节点中。
现在来处理旧节点并创建一个新的节点：

1. +void leaf_node_split_and_insert(Cursor* cursor, uint32_t key, Row* value) {
2. +  /*
3. +  Create a new node and move half the cells over.
4. +  Insert the new value in one of the two nodes.
5. +  Update parent or create a new parent.
6. +  */
7. +
8. +  void* old_node = get_page(cursor->table->pager, cursor->page_num);
9. +  uint32_t new_page_num = get_unused_page_num(cursor->table->pager);
10. +  void* new_node = get_page(cursor->table->pager, new_page_num);
11. +  initialize_leaf_node(new_node);

复制代码

接下来，拷贝节点中每一个单元格到新的位置：

1. +  /*
2. +  All existing keys plus new key should be divided
3. +  evenly between old (left) and new (right) nodes.
4. +  Starting from the right, move each key to correct position.
5. +  */
6. +  for (int32_t i = LEAF_NODE_MAX_CELLS; i >= 0; i--) {
7. +    void* destination_node;
8. +    if (i >= LEAF_NODE_LEFT_SPLIT_COUNT) {
9. +      destination_node = new_node;
10. +    } else {
11. +      destination_node = old_node;
12. +    }
13. +    uint32_t index_within_node = i % LEAF_NODE_LEFT_SPLIT_COUNT;
14. +    void* destination = leaf_node_cell(destination_node, index_within_node);
15. +
16. +    if (i == cursor->cell_num) {
17. +      serialize_row(value, destination);
18. +    } else if (i > cursor->cell_num) {
19. +      memcpy(destination, leaf_node_cell(old_node, i - 1), LEAF_NODE_CELL_SIZE);
20. +    } else {
21. +      memcpy(destination, leaf_node_cell(old_node, i), LEAF_NODE_CELL_SIZE);
22. +    }
23. +  }

复制代码

更新节点中头部标记的单元格的数量（更新node’s header）

1. +  /* Update cell count on both leaf nodes */
2. +  *(leaf_node_num_cells(old_node)) = LEAF_NODE_LEFT_SPLIT_COUNT;
3. +  *(leaf_node_num_cells(new_node)) = LEAF_NODE_RIGHT_SPLIT_COUNT;

复制代码

然后我们需要更新节点的父节点。如果原始节点是一个根节点（root node），那么他就没有父节点。这种情况中，创建一个新的根节点来作为它的父节点。这里做另外一个存根（先不具体实现）：

1. +  if (is_node_root(old_node)) {
2. +    return create_new_root(cursor->table, new_page_num);
3. +  } else {
4. +    printf("Need to implement updating parent after split\n");
5. +    exit(EXIT_FAILURE);
6. +  }
7. +}

复制代码

分配新的页面（Allocating New Pages）

让我们回过头来定义一些函数和常量。当我们创建一个新的叶子节点，我们把它放进一个由get_unused_page_num()函数决定(返回)的页中。

1. +/*
2. +Until we start recycling free pages, new pages will always
3. +go onto the end of the database file
4. +*/
5. +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 个原有的单元格和一个新插入的单元格）。如果 N+1 是奇数，我比较随意地选择了左侧节点获取多的那个单元格。

1. +const uint32_t LEAF_NODE_RIGHT_SPLIT_COUNT = (LEAF_NODE_MAX_CELLS + 1) / 2;
2. +const uint32_t LEAF_NODE_LEFT_SPLIT_COUNT =
3. +    (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 属性的情况下，新的树仍然保持了高度上平衡。
此时，我们已经分配了右子节点并移动高半部分的条目到这个子节点。我们的函数把这个右子节点作为输入，并且分配一个新的页面来存放左子节点。

1. +void create_new_root(Table* table, uint32_t right_child_page_num) {
2. +  /*
3. +  Handle splitting the root.
4. +  Old root copied to new page, becomes left child.
5. +  Address of right child passed in.
6. +  Re-initialize root page to contain the new root node.
7. +  New root node points to two children.
8. +  */
9. +
10. +  void* root = get_page(table->pager, table->root_page_num);
11. +  void* right_child = get_page(table->pager, right_child_page_num);
12. +  uint32_t left_child_page_num = get_unused_page_num(table->pager);
13. +  void* left_child = get_page(table->pager, left_child_page_num);

复制代码

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

1. +  /* Left child has data copied from old root */
2. +  memcpy(left_child, root, PAGE_SIZE);
3. +  set_node_root(left_child, false);

复制代码

最后我们初始化根节点作为一个新的、有两个子节点的内部节点。

1. +  /* Root node is a new internal node with one key and two children */
2. +  initialize_internal_node(root);
3. +  set_node_root(root, true);
4. +  *internal_node_num_keys(root) = 1;
5. +  *internal_node_child(root, 0) = left_child_page_num;
6. +  uint32_t left_child_max_key = get_node_max_key(left_child);
7. +  *internal_node_key(root, 0) = left_child_max_key;
8. +  *internal_node_right_child(root) = right_child_page_num;
9. +}

复制代码

内部节点格式（Internal Node Format）

现在我们终于创建了内部节点，我们就不得不定义它的布局了。它从通用 header 开始，然后是它包含的 key 的数量，接下来是它右边子节点的页号。内部节点的子节点指针始终比它的 key 的数量多一个。这个 子节点指针存储在 header 中。

1. +/*
2. + * Internal Node Header Layout
3. + */
4. +const uint32_t INTERNAL_NODE_NUM_KEYS_SIZE = sizeof(uint32_t);
5. +const uint32_t INTERNAL_NODE_NUM_KEYS_OFFSET = COMMON_NODE_HEADER_SIZE;
6. +const uint32_t INTERNAL_NODE_RIGHT_CHILD_SIZE = sizeof(uint32_t);
7. +const uint32_t INTERNAL_NODE_RIGHT_CHILD_OFFSET =
8. +    INTERNAL_NODE_NUM_KEYS_OFFSET + INTERNAL_NODE_NUM_KEYS_SIZE;
9. +const uint32_t INTERNAL_NODE_HEADER_SIZE = COMMON_NODE_HEADER_SIZE +
10. +                                           INTERNAL_NODE_NUM_KEYS_SIZE +
11. +                                           INTERNAL_NODE_RIGHT_CHILD_SIZE;

复制代码

内部节点的 body 是一个单元格的数组，每个单元格包含一个子指针和一个 key 。每个 key 都必须是它的左边子节点中包含的最大 key 。

1. +/*
2. + * Internal Node Body Layout
3. + */
4. +const uint32_t INTERNAL_NODE_KEY_SIZE = sizeof(uint32_t);
5. +const uint32_t INTERNAL_NODE_CHILD_SIZE = sizeof(uint32_t);
6. +const uint32_t INTERNAL_NODE_CELL_SIZE =
7. +    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 对数据库来说是很有用的数据结构。
下边是读取和写入一个内部节点的方法：

1. +uint32_t* internal_node_num_keys(void* node) {
2. +  return node + INTERNAL_NODE_NUM_KEYS_OFFSET;
3. +}
4. +
5. +uint32_t* internal_node_right_child(void* node) {
6. +  return node + INTERNAL_NODE_RIGHT_CHILD_OFFSET;
7. +}
8. +
9. +uint32_t* internal_node_cell(void* node, uint32_t cell_num) {
10. +  return node + INTERNAL_NODE_HEADER_SIZE + cell_num * INTERNAL_NODE_CELL_SIZE;
11. +}
12. +
13. +uint32_t* internal_node_child(void* node, uint32_t child_num) {
14. +  uint32_t num_keys = *internal_node_num_keys(node);
15. +  if (child_num > num_keys) {
16. +    printf("Tried to access child_num %d > num_keys %d\n", child_num, num_keys);
17. +    exit(EXIT_FAILURE);
18. +  } else if (child_num == num_keys) {
19. +    return internal_node_right_child(node);
20. +  } else {
21. +    return internal_node_cell(node, child_num);
22. +  }
23. +}
24. +
25. +uint32_t* internal_node_key(void* node, uint32_t key_num) {
26. +  return internal_node_cell(node, key_num) + INTERNAL_NODE_CHILD_SIZE;
27. +}

复制代码

对于一个内部节点，最大 key 始终是其右键。对于一个叶子节点，最大 key 就是最大索引键。

1. +uint32_t get_node_max_key(void* node) {
2. +  switch (get_node_type(node)) {
3. +    case NODE_INTERNAL:
4. +      return *internal_node_key(node, *internal_node_num_keys(node) - 1);
5. +    case NODE_LEAF:
6. +      return *leaf_node_key(node, *leaf_node_num_cells(node) - 1);
7. +  }
8. +}

复制代码

追踪根节点（Keeping Track of the Root）

我们终于在通用的节点 header 中使用了 is_root 字段。回调它是我们用它来决定怎样来分裂一个叶子节点：

1.     if (is_node_root(old_node)) {
2.         return create_new_root(cursor->table, new_page_num);
3.     } else {
4.         printf("Need to implement updating parent after split\n");
5.         exit(EXIT_FAILURE);
6.     }
7. }

复制代码

下面是 getter & setter：

1. +bool is_node_root(void* node) {
2. +  uint8_t value = *((uint8_t*)(node + IS_ROOT_OFFSET));
3. +  return (bool)value;
4. +}
5. +
6. +void set_node_root(void* node, bool is_root) {
7. +  uint8_t value = is_root;
8. +  *((uint8_t*)(node + IS_ROOT_OFFSET)) = value;
9. +}

复制代码

初始化这两种类型的节点（内部节点&叶子节点）应默认设置 is_root 为 false。

1. void initialize_leaf_node(void* node) {
2.   set_node_type(node, NODE_LEAF);
3. +  set_node_root(node, false);
4.   *leaf_node_num_cells(node) = 0;
5. }
7. +void initialize_internal_node(void* node) {
8. +  set_node_type(node, NODE_INTERNAL);
9. +  set_node_root(node, false);
10. +  *internal_node_num_keys(node) = 0;
11. +}

复制代码

当创建表的第一个节点时我们需要设置 is_root 为 true 。

1. // New database file. Initialize page 0 as leaf node.
2. void* root_node = get_page(pager, 0);
3. initialize_leaf_node(root_node);
4. +    set_node_root(root_node, true);
5. }
7. return table;

复制代码

打印树（Printing the Tree）

为了帮助我们可视化数据库的状态，我们应该更新我们的 .btree 元命令以打印多级树。
我要替换当前的 print_leaf_node（） 函数：

1. -void print_leaf_node(void* node) {
2. -  uint32_t num_cells = *leaf_node_num_cells(node);
3. -  printf("leaf (size %d)\n", num_cells);
4. -  for (uint32_t i = 0; i < num_cells; i++) {
5. -    uint32_t key = *leaf_node_key(node, i);
6. -    printf("  - %d : %d\n", i, key);
7. -  }
8. -}

复制代码

实现一个递归函数，可以接受任何节点，然后打印它和它的子节点。它接受一个缩进级别作为参数，缩进级别每次在每次递归时会递增。我还在缩进中添加了一个很小的辅助函数。

1. +void indent(uint32_t level) {
2. +  for (uint32_t i = 0; i < level; i++) {
3. +    printf("  ");
4. +  }
5. +}
6. +
7. +void print_tree(Pager* pager, uint32_t page_num, uint32_t indentation_level) {
8. +  void* node = get_page(pager, page_num);
9. +  uint32_t num_keys, child;
10. +
11. +  switch (get_node_type(node)) {
12. +    case (NODE_LEAF):
13. +      num_keys = *leaf_node_num_cells(node);
14. +      indent(indentation_level);
15. +      printf("- leaf (size %d)\n", num_keys);
16. +      for (uint32_t i = 0; i < num_keys; i++) {
17. +        indent(indentation_level + 1);
18. +        printf("- %d\n", *leaf_node_key(node, i));
19. +      }
20. +      break;
21. +    case (NODE_INTERNAL):
22. +      num_keys = *internal_node_num_keys(node);
23. +      indent(indentation_level);
24. +      printf("- internal (size %d)\n", num_keys);
25. +      for (uint32_t i = 0; i < num_keys; i++) {
26. +        child = *internal_node_child(node, i);
27. +        print_tree(pager, child, indentation_level + 1);
28. +
29. +        indent(indentation_level + 1);
30. +        printf("- key %d\n", *internal_node_key(node, i));
31. +      }
32. +      child = *internal_node_right_child(node);
33. +      print_tree(pager, child, indentation_level + 1);
34. +      break;
35. +  }
36. +}

复制代码

并更新对 print 函数的调用，传递缩进级别为零。

1. } else if (strcmp(input_buffer->buffer, ".btree") == 0) {
2.   printf("Tree:\n");
3. -    print_leaf_node(get_page(table->pager, 0));
4. +    print_tree(table->pager, 0, 0);
5.   return META_COMMAND_SUCCESS;

复制代码

下面是一个对新的打印函数的测例

1. +  it 'allows printing out the structure of a 3-leaf-node btree' do
2. +    script = (1..14).map do |i|
3. +      "insert #{i} user#{i} person#{i}@example.com"
4. +    end
5. +    script << ".btree"
6. +    script << "insert 15 user15 person15@example.com"
7. +    script << ".exit"
8. +    result = run_script(script)
9. +
10. +    expect(result[14...(result.length)]).to match_array([
11. +      "db > Tree:",
12. +      "- internal (size 1)",
13. +      "  - leaf (size 7)",
14. +      "    - 1",
15. +      "    - 2",
16. +      "    - 3",
17. +      "    - 4",
18. +      "    - 5",
19. +      "    - 6",
20. +      "    - 7",
21. +      "  - key 7",
22. +      "  - leaf (size 7)",
23. +      "    - 8",
24. +      "    - 9",
25. +      "    - 10",
26. +      "    - 11",
27. +      "    - 12",
28. +      "    - 13",
29. +      "    - 14",
30. +      "db > Need to implement searching an internal node",
31. +    ])
32. +  end

复制代码

哦吼！是谁写的TODO信息？（作者在故弄玄虚！明明是他自己在 table_find() 函数中把内部节点搜索的功能存根的！）
下次我们将通过在多级树上实现搜索来继续史诗般的 B 树传奇。

Enjoy GreatSQL
来源:https://www.cnblogs.com/greatsql/p/17121669.html
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！