Lab 2.3 范围查询

1 概述

还记得我们对Skiplist实现了前缀查询和谓词查询吗, 他们本质上都是范围查询, 这一小节, 你将基于已有的Skiplist的前缀查询和谓词查询接口, 实现MemTable的谓词查询。

本小节需要你修改的代码： -src/memtable/memtable.cpp

• include/memtable/memtable.h (Optional)

2 实现 iters_preffix

HeapIterator MemTable::iters_preffix(const std::string &preffix,
                                     uint64_t tranc_id) {

  // TODO Lab 2.3 MemTable 的前缀迭代器

  return {};
}

你需要借助Skiplist的begin_preffix完成这个MemTable::iters_preffix, 你可以从返回值类型推断出, 我们仍然需要借助HeapIterator进行去重和排序。

这里需要注意的还是自定义的排序id(就是SearchItem里面的成员变量idx_), 你需要在构造HeapIterator手动赋予idx_正确的整型值。

另外，tranc_id相关的滤除操作你可以暂时忽略, 直接传入SearchItem的构造函数即可。

需要注意的是, 这个返回的迭代器从语义上是begin迭代器, 其使用方式是判断自身是否is_valid()以及is_end(), 不同于C++ STL中给定一对迭代器确定范围的风格。这也算是作者前期项目设计的不足之处，介于次代码和实验还是初版，能用能跑就行。

3 实现 iters_monotony_predicate

std::optional<std::pair<HeapIterator, HeapIterator>>
MemTable::iters_monotony_predicate(
    uint64_t tranc_id, std::function<int(const std::string &)> predicate) {
  // TODO Lab 2.3 MemTable 的谓词查询迭代器起始范围
  return std::nullopt;
}

和iters_preffix类似, 只不过查询逻辑从特化的前缀查询变成了适用性更广泛的谓词查询, 注意事项也都差不多, 同样是借助Skiplist的iters_monotony_predicate(predicate)获取初步的结果, 再用HeapIterator区中。

4 测试

完成上面的函数后, 你应该可以通过所有的test/test_memtable.cpp的单元测试:

✗ xmake
✗ xmake run test_memtable
[==========] Running 12 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 12 tests from MemTableTest
[ RUN      ] MemTableTest.BasicOperations
[       OK ] MemTableTest.BasicOperations (0 ms)
[ RUN      ] MemTableTest.RemoveOperations
[       OK ] MemTableTest.RemoveOperations (0 ms)
[ RUN      ] MemTableTest.FrozenTableOperations
[       OK ] MemTableTest.FrozenTableOperations (0 ms)
[ RUN      ] MemTableTest.LargeScaleOperations
[       OK ] MemTableTest.LargeScaleOperations (1 ms)
[ RUN      ] MemTableTest.MemorySizeTracking
[       OK ] MemTableTest.MemorySizeTracking (0 ms)
[ RUN      ] MemTableTest.MultipleFrozenTables
[       OK ] MemTableTest.MultipleFrozenTables (0 ms)
[ RUN      ] MemTableTest.IteratorComplexOperations
[       OK ] MemTableTest.IteratorComplexOperations (0 ms)
[ RUN      ] MemTableTest.ConcurrentOperations
[       OK ] MemTableTest.ConcurrentOperations (604 ms)
[ RUN      ] MemTableTest.PreffixIter
[       OK ] MemTableTest.PreffixIter (0 ms)
[ RUN      ] MemTableTest.IteratorPreffix
[       OK ] MemTableTest.IteratorPreffix (0 ms)
[ RUN      ] MemTableTest.ItersPredicate_Base
[       OK ] MemTableTest.ItersPredicate_Base (0 ms)
[ RUN      ] MemTableTest.ItersPredicate_Large
[       OK ] MemTableTest.ItersPredicate_Large (13 ms)
[----------] 12 tests from MemTableTest (620 ms total)

[----------] Global test environment tear-down
[==========] 12 tests from 1 test suite ran. (620 ms total)
[  PASSED  ] 12 tests.

到此为止, Lab2的实验结束, 恭喜你完成本实验!