- GreatSQL社區原創內容未經授權不得隨意使用，轉載請聯系小編并注明來源，
- GreatSQL是MySQL的國產分支版本，使用上與MySQL一致，
- 作者： 花家舍
- 文章來源：GreatSQL社區原創
前文回顧
- 實作一個簡單的Database系列
譯注：cstack在github維護了一個簡單的、類似sqlite的資料庫實作，通過這個簡單的專案，可以很好的理解資料庫是如何運行的，本文是第十一篇，主要是實作遞回搜索B-Tree
Part 11 遞回搜索B-Tree
上次我們在插入第15行資料報錯的時候結束：
db > insert 15 user15 [email protected]
Need to implement searching an internal node
首先，使用一個新的函式呼叫替換埋樁的代碼，
if (get_node_type(root_node) == NODE_LEAF) {
return leaf_node_find(table, root_page_num, key);
} else {
- printf("Need to implement searching an internal node\n");
- exit(EXIT_FAILURE);
+ return internal_node_find(table, root_page_num, key);
}
}
這個函式會執行二叉搜索來查找子節點是否會包含給定的 Key，請記住，這些指向右子節點的 Key 都是他們指向的子節點中包含的最大 Key ，
three-level btree
所以我們的二叉搜索比較查找的 Key 和指向右邊子節點的的指標，
+Cursor* internal_node_find(Table* table, uint32_t page_num, uint32_t key) {
+ void* node = get_page(table->pager, page_num);
+ uint32_t num_keys = *internal_node_num_keys(node);
+
+ /* Binary search to find index of child to search */
+ uint32_t min_index = 0;
+ uint32_t max_index = num_keys; /* there is one more child than key */
+
+ while (min_index != max_index) {
+ uint32_t index = (min_index + max_index) / 2;
+ uint32_t key_to_right = *internal_node_key(node, index);
+ if (key_to_right >= key) {
+ max_index = index;
+ } else {
+ min_index = index + 1;
+ }
+ }
另請記住，內部節點的子節點可以是葉節點，也可以是內部節點，在我們查找到正確的子節點后，會在節點上呼叫適合的搜索函式：
+ uint32_t child_num = *internal_node_child(node, min_index);
+ void* child = get_page(table->pager, child_num);
+ switch (get_node_type(child)) {
+ case NODE_LEAF:
+ return leaf_node_find(table, child_num, key);
+ case NODE_INTERNAL:
+ return internal_node_find(table, child_num, key);
+ }
+}
測驗
現在向一個多節點btree插入 key 不再會導致報錯結果，所以我們可以更新我們的測例：
" - 12",
" - 13",
" - 14",
- "db > Need to implement searching an internal node",
+ "db > Executed.",
+ "db > ",
])
end
我覺得現在是反思一下我們的另一個測驗的時候了，也就是嘗試插入1400行資料，仍然會報錯，但是報錯資訊變成新的其他報錯，現在，當程式 crash 的時候，我們的測驗不能很好的處理這種報錯，如果發生這種報錯情況，到目前為止我們只使用獲得的輸出，
raw_output = nil
IO.popen("./db test.db", "r+") do |pipe|
commands.each do |command|
- pipe.puts command
+ begin
+ pipe.puts command
+ rescue Errno::EPIPE
+ break
+ end
end
pipe.close_write
下面顯示出了我們在測驗插入1400行時輸出的報錯：
end
script << ".exit"
result = run_script(script)
- expect(result[-2]).to eq('db > Error: Table full.')
+ expect(result.last(2)).to match_array([
+ "db > Executed.",
+ "db > Need to implement updating parent after split",
+ ])
end
看起來這是我們待辦事項串列中的下一個！
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/546372.html
標籤：MySQL
上一篇：MySQL基本命令操作
下一篇：1 MySql基礎介紹