原文連結：https://juejin.cn/post/7139572163371073543

專案准備

本文對應 2022 年的課程，Project 0 已經更新為實現字典樹了。C++17 的開發環境建議直接下載 CLion，不建議自己瞎折騰。

測試

$ mkdir build && cd build
$ cmake -DCMAKE_BUILD_TYPE=DEBUG ..
$ make starter_trie_test 
$ ./test/starter_trie_test

執行上面的指令，你會得到如下輸出，這不表示該專案的 5 個測試用例沒過，而是沒有執行。

[==========] Running 0 tests from 0 test suites.
[==========] 0 tests from 0 test suites ran. (0 ms total)
[ PASSED ] 0 tests.

YOU HAVE 5 DISABLED TESTS

需要修改 test/primer/starter_trie_test.cpp 檔案，移除測試名 DISABLED_ 字首。

// TEST(StarterTest, DISABLED_TrieNodeInsertTest)
TEST(StarterTest, TrieNodeInsertTest)

格式化

$ make format 
$ make check-lint 
$ make check-clang-tidy-p0

偵錯紀錄檔

LOG_INFO("# Pages: %d", num_pages);
LOG_DEBUG("Fetching page %d", page_id);

專案介紹

使用支援並行的字典樹實現一個鍵值儲存，字典樹是一種高效的排序樹，用於檢索指定鍵值。這裡假設鍵都是非空的可變長度字串，但事實上鍵可以是任意型別。

上圖所示字典樹中儲存了：HAT、HAVE、HELLO 三個鍵。

上圖所示字典樹儲存了：ab=1、ac="val" 兩組鍵值。

專案實現

只需要修改一個檔案：src/include/primer/p0_trie.h

專案已經定義好了類和成員變數，以及需要實現的成員函數的簽名，可以新增輔助變數或函數，但不能修改已有變數和函數簽名。

任務一

檔案中定義了 Trie、TrieNode、TrieNodeWithValue 三個類，建議先實現單執行緒版本，再改並行版本，類中的成員變數和成員函數都有註釋。

任務二

實現並行安全的字典樹，可以使用 BusTub 的 RwLatch 或 C++ 的 std::shared_mutex。

一些 C++ 的基操

一年多沒寫 C++ 了，用慣了 Go，突然用 C++ 寫的腦殼疼，沒用過 C++ 的小夥伴可能想編譯通過都費勁，這裡貼一下需要了解的 C++ 特性。

移動語意

std::unique_ptr<T> 表示唯一的指向型別為 T 的物件的指標，因此需要使用移動語意 std::move，程式碼中 children_ 的型別巢狀了 std::unique_ptr<T>，也需要使用移動語意。

TrieNode(TrieNode &&other_trie_node) noexcept {
    key_char_ = other_trie_node.key_char_;
    is_end_ = other_trie_node.is_end_;
    children_ = std::move(other_trie_node.children_);
}

構造父類別

TrieNodeWithValue 是 TrieNode 的子類，構造子類時，如果沒有手動在子類別建構函式中構造父類別，就會呼叫父類別的預設建構函式，而程式碼中父類別是沒有預設建構函式的，所以需要手動在子類中構造父類別。

需要使用 std::forward<TrieNode> 轉發右值參照。

TrieNodeWithValue(TrieNode &&trieNode, T value) : TrieNode(std::forward<TrieNode>(trieNode)) {
    this->value_ = value;
    this->is_end_ = true;
}

父子指標轉換

TrieNodeWithValue 是模板類，沒法辦使用多型，Trie::GetValue 需要將 unique_ptr<TrieNode> 轉換為 TrieNodeWithValue<T>* 後呼叫 TrieNodeWithValue::GetValue。

std::unique_ptr<TrieNode> uptr = std::make_unique<TrieNodeWithValue<T>>('a', T());
dynamic_cast<TrieNodeWithValue<T>*>(&(*uptr))->GetValue();

可能有更優雅的辦法，但我實在是想不出來了，C++ 可真難寫啊。

所有權規避

std::unique_ptr<T> 的傳遞一定是使用移動語意轉移 T 物件地址的所有權，但也可以不獲取所有權存取 T 物件的地址，程式碼裡的註釋也引導我們使用這種方式。

std::unique_ptr<int> uptr(new int(1));
std::cout << *uptr << std::endl; // 1

auto *p = &uptr;
*(*p) = 2;
std::cout << *uptr << std::endl; // 2

程式碼實現

大部分程式碼按照註釋一步一步來就沒問題，課程規定不公開程式碼，所以這裡只列一些難點。

迴圈迭代

這裡給出一個模版，對於尾節點和非尾節點，一般需要不同的操作。

auto curr = &root_;
size_t i = 0;

while (i + 1 < key.size()) {
    curr = (*curr)->GetChildNode(key[i]);
    i++;
}
// end_node
curr = (*curr)->GetChildNode(key[i]);

節點轉換

在插入流程中，當迭代到最後一個字元時，發現已經有了一個 TrieNode 型別的節點，需要轉換為 TrieNodeWithValue 型別。

* When you reach the ending character of a key:
* 2. If the terminal node is a TrieNode, then convert it into TrieNodeWithValue by
* invoking the appropriate constructor.

不熟悉 C++ 的話這個操作可能有點困難，這裡給出程式碼，這一層又一層的括號和解除參照確實不夠優雅，但一時間也想不到其他好辦法。

(*curr) = std::make_unique<TrieNodeWithValue<T>>(std::move(*(*curr)), value);

節點刪除

根據程式碼註釋的提示，Remove 函數是要遞迴刪除的，這裡給出遞迴的框架。

bool remove_inner(const std::string &key, size_t i, std::unique_ptr<TrieNode> *curr, bool *success) {
  if (i == key.size()) {
    *success = true; // Remove 的返回值，表示成功刪除
    (*curr)->SetEndNode(false);
    return !(*curr)->HasChildren() && !(*curr)->IsEndNode();
  }

  bool can_remove = remove_inner(key, i + 1, (*curr)->GetChildNode(key[i]), success);

  if (can_remove) {
    (*curr)->RemoveChildNode(key[i]);
  }
  return !(*curr)->HasChildren() && !(*curr)->IsEndNode();
}

remove_innner 的返回值表示傳入節點是否可以刪除，可以刪除的條件是該節點無子節點且非尾節點。函數內判斷當前節點的子節點是否可以刪除，並返回當前節點是否可以刪除。出口是遞迴到了傳入 key 的尾節點，取消尾節點標記，並返回是否可以刪除。該函數呼叫前還需要判斷一下 key 是否存在。

空模板變數值

GetValue 的返回值是一個模板型別，錯誤的時候直接 return T()，正常情況下，需要轉換 TrieNode 為 TrieNodeWithValue 中獲取值，上文提過該父子類轉換的辦法。

template <typename T>
T GetValue(const std::string &key, bool *success) {
    return T();
    return dynamic_cast<TrieNodeWithValue<T> *>(&(*(*curr)))->GetValue();
}

並行安全

這個其實很簡單，前 4 個測試都通過了，Insert、Remove、GetValue 三個函數開始和結束位置加鎖和解鎖就可以了，需要注意的是這三個函數如果彼此呼叫會死鎖，比如 Insert 裡面呼叫 GetValue 判斷 key 是否存在。

這裡提供一個 Go 語言中 defer 解鎖的簡易實現，如果你不知道 defer 就在每個返回的地方都解鎖就可以。

class RLock {
  ReaderWriterLatch *latch_;

 public:
  RLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->RLock(); }
  ~RLock() { latch_->RUnlock(); }
};

class WLock {
  ReaderWriterLatch *latch_;

 public:
  WLock(ReaderWriterLatch *latch) : latch_(latch) { latch_->WLock(); }
  ~WLock() { latch_->WUnlock(); }
};

使用方式如下，以 Remove 為例。

bool Remove(const std::string &key) {
  WLock w(&latch_);

  if (!Exist(key)) {
    return false;
  }
  bool success = false;
  remove_inner(key, 0, &root_, &success);
  return success;
}

寫在最後

動手開始專案前，可以先去 leetcode 過一遍實現 Trie (字首樹)，先能寫出簡單的字典樹再動手。如果需要程式碼的話可以私信我。如果想做資料庫的工作歡迎找我內推（_{恰點內推獎金}）。

CMU 15-445 Project 0 實現字典樹