Trie

trie 实现的是键值存储，字符串键可以映射到任何类型值。键的值存储在改键的最后一个字符的终端节点。例如将（“ab”， 1） 和 （“ac”， “val”） 插入到 trie 中。

copy-on-write

写时复制，任何操作都不会修改原先的trie节点，而是会为修改后的数据创建新节点，并为修改后的trie返回新的根节点。这样做可以很方便的访问旧的trie，撤销操作也容易。

插入

例如对之前的trie插入（“ad”， 2），这里会复用原先树中的两个字节点，并创建一个新的值节点2，然后用他们三个来创建新的Node2。

然后插入（“b”， 3），创建一个新的root、一个新的值节点3并复用之前的节点。这样操作前后的内容，只要有root，就可以访问当时的完整数据。

删除

父节点也可以有值，例如上述trie可以插入（“a”， “abc”）。删除的时候先删除对应的节点，之后要注意的是，需要清除所有不必要的节点（即没有值且没有子节点的节点）。

implement

Get(key)

获取 key 对应的值。

1. 遍历key的每一个字符，从当前root开始，通过查看每个字符是否在current->children_中，没找到或者current为空直接返回nullptr，找到了就把current更新为current->children_.at(ch)。
2. 经过上一步骤之后，现在current就是key对应的值节点。然后利用dynamic_cast把它转换为const TrieNodeWithValue<T> *。若是转换后为nullptr，说明类型不匹配，直接返回nullptr，否则返回该节点。

1

auto *node{dynamic_cast<const TrieNodeWithValue<T> *>(current.get())};

Put(key, value)

为 key 设置对应的值。如果键已存在，则覆盖现有值。请注意，值的类型可能是不可复制的（即 std：：unique_ptr）。此方法返回一个新的 trie。

1. 如果key.empty()。判断root是否有孩子，若有孩子，用孩子和传入的value创建一个new_root返回，否则直接用value创建new_root返回。

1
2
3
4
5

    if (root_->children_.empty()) {
      new_root = std::make_unique<TrieNodeWithValue<T>>(std::move(val_p));
    } else {
      new_root = std::make_unique<TrieNodeWithValue<T>>(root_->children_, std::move(val_p));
    }

2. 利用节点的Clone()函数，从root开始克隆，先判断root是否存在，若不存在则用std::make_shared<TrieNode>()新建一个TrieNode。该节点即为一会要返回的新的root。

3. 开始遍历key。每次遍历，先判断若当前字符不是key的最后一个字符，进行下述操作：在当前节点clone_current的孩子中找，若找到了则把这个孩子Clone()一份作为clone_current的新孩子，然后更新clone_current为这个孩子，继续往下找。若没找到该孩子，则创建一个新的TrieNode。

4. 若是遍历到最后一个字符，判断是否有对应的孩子，同理1，若有则用这个孩子的children_和传入的value创建一个TrieNodeWithValue，若没有就直接用value创建。建好了之后连上当前的clone_current->children_[ch] = new_child就大功告成。返回新的root。

Remove(key)

删除 key 的值。此方法返回一个新的 trie。

1. 还是先处理边界情况，若!root_直接返回*this。若key.empty()：先克隆当前root，有孩子就用孩子创建一个无值节点返回，没孩子直接返回nullptr。
2. 开始遍历key，任何一个节点没找到则直接返回*this，并把路上经过的每一个节点克隆一遍放入一个vector（或者直接用stack）中，并前后连接上。遍历完后把最后一个节点的is_value_node置为false。

1
2
3
4

    // clone every node in key into vec.
    clone_current = std::shared_ptr<TrieNode>(current->Clone());
    vec.back()->children_[ch] = clone_current;
    vec.push_back(clone_current);

3. 自底向上删除，从vector的最后一个节点往前。若!is_value_node：判断若没有孩子，则erase掉该节点，否则用孩子创建一个TrieNode的无值节点替换。
4. 判断新root是否为空且!is_value_node，若满足则返回nullptr。否则返回新root。

注意

• 所有操作都不会在原始trie上修改，应该是创建一个新的trie节点并尽可能复用旧的trie节点。
• 创建新节点时将其转换为智能指针，复用节点时可以复制std::shared_ptr<TrieNode>，智能共享指针的增加不会复制底层数据，且会在没有人引用底层对象时自动释放对象。
• std::move()可以把左值转换为右值。

Concurrent Key-Value Store

Triestore

在拥有可在单线程环境中使用的写入时复制trie后，为多线程环境实现并发键值存储。并发键值存储应同时为多个读取器和单个写入器提供服务。

此外，如果我们从trie获得对值的引用，那么无论我们如何修改 trie，我们都应该能够访问它。Trie的Get函数仅返回一个指针。如果存储此值的trie节点已被删除，则指针将悬空。因此，在 TrieStore 中，我们返回一个ValueGuard，它存储对值的引用和对应于 trie 结构根的TrieNode，以便在我们存储ValueGuard时可以访问该值。

implement

Get(key)

1. 拿到root lock，获取root，然后释放root lock。注意在持有root lock的时候，先不要查找trie里的值。
2. 查找trie里的值。
3. 如果找到值了，返回一个ValueGuard对象，它持有对值的引用和对应的root，否则返回std::nullopt。

Put(key, value)

1. 获取write_lock_，执行put。
2. 获取root lock，修改root_为新的root。

Remove(key)

1. 获取write_lock_，执行remove。
2. 获取root lock，修改root_为新的root。

SQL String Functions

需要实现上层和下层SQL函数。这可以分2个步骤完成：

• 在 string_expression.h 中实现函数逻辑。
• 在 BusTub 中注册函数，以便 SQL 框架可以在用户执行 SQL 时以 plan_func_call.cpp 调用你的函数。

实现函数逻辑

简单的大小写转换，利用std::toupper和std::tolower。

注册函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

auto Planner::GetFuncCallFromFactory(const std::string &func_name, std::vector<AbstractExpressionRef> args)
    -> AbstractExpressionRef {
  // 1. check if the parsed function name is "lower" or "upper".
  // 2. verify the number of args (should be 1), refer to the test cases for when you should throw an `Exception`.
  // 3. return a `StringExpression` std::shared_ptr.
  if ((func_name == "lower" || func_name == "upper") && args.size() == 1) {
    return static_cast<std::shared_ptr<StringExpression>>(std::make_shared<StringExpression>(
        args[0], func_name == "lower" ? StringExpressionType::Lower : StringExpressionType::Upper));
  }
  throw Exception(fmt::format("func call {} not supported in planner yet", func_name));
}