- 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 divided
+ evenly 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 個原有的單元格和一個新插入的單元格），如果 N+1 是奇數，我比較隨意地選擇了左側節點獲取多的那個單元格，
+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 layers | max # leaf nodes | Size of all leaf nodes |
|---|---|---|
| 0 | 511^0 = 1 | 4 KB |
| 1 | 511^1 = 512 | ~2 MB |
| 2 | 511^2 = 261,121 | ~1 GB |
| 3 | 511^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 = https://www.cnblogs.com/greatsql/archive/2023/02/15/*((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' do
+ script = (1..14).map do |i|
+ "insert #{i} user#{i} person#{i}@example.com"
+ end
+ script << ".btree"
+ script << "insert 15 user15 [email protected]"
+ script << ".exit"
+ result = 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 [email protected]
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-100-1-1.html
技術交流群：
微信：掃碼添加
GreatSQL社區助手微信好友，發送驗證資訊加群，
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/544065.html
標籤：其他
上一篇：[20230214]訪問asm相關視圖緩慢的分析2.txt
下一篇：MySQL使用筆記