最近完整一次对范围扫描的小改动，这里记录一下，顺便讲讲范围扫描的实现
实现
总的来讲 mace 的范围扫描实现其实很简单：输入一个范围，使用左边界在树中查找，如果找到了节点，就取key出来直到key超过了右边界，或者节点遍历完成，这时候使用节点的 high key 继续查找，重复前面的过程直到key超过右边界
注意到，这里的实现并没有利用 B+ 树叶子节点间的指针，这是有原因的：因为树是可以被并发修改的，如果在scan过程中有节点分裂/合并（SMO）发生，那么叶子节点间的指针就会失效
小小的优化
这里的优化主要是两部分： 1. 缓存 node 2. 缓存 key
前面提到树是可以并发修改的，那是否意味着iterator的每个 next 都需要判断一下树是否修改了？通常来讲，回答是肯定的（比如 Sled 的实现），在 mace 中一个 node 由 base 和 delta 两部分组成，在树发生 SMO 时虽然会在 page table 中替换掉旧的 page，但在 mace 中的 node 中的 base 和 delta 的数据都是由 node 内部独立的部件管理的，因此只需要在 iterator 中存放 node 的一个 clone，在发生SMO时这个 clone 仍然是可用的，因此不需要每次 next 都检查是否发生了 SMO，而 SMO 的影响则是：在查找到node的 successor 后可能需要跳过新插入的元素
同时由于 MVCC 的支持，不管是否发生 SMO，iterator 看到的数据总是一致的
另外, mace 目前没有配置允许用户禁用掉 prefix encode，因此在 scan 的过程中无法避免将 node 中 key 的 prefix 和 base 做合并操作，这就会带来频繁的内存分配和拷贝的开销。因此 mace 在 iterator 中增加了 cached_key 成员，用于在整个 iterator 的生命周期内负责对 prefix 和 base 的拼接工作，以减少内存分配
scan 和 rocksdb 的对比
rocksdb 和 mace 的不同点是：rocksdb 的内存数据结构和磁盘数据结构是不同的，而 mace 中尽管内存中分了 base 和 delta，但本质上都是 B+ 树的节点。rocksdb 的这个不同点的结果是：扫描 memtable 的速度远大于 sst 的，主要有两个点： 1. memtable 没有 prefix encode，即：存放的是完整的 key，而 sst 是有 prefix encode 的，分为 shared 和 no-share 两个部分，因此也需要拼接 2. 对于大 value 来说，blobdb 还多了一层 indirection，value 需要通过 indirection 到 blob 文件中获取
就 scan 和 mace 对比的话：
1. 如果数据都在内存中，mace 是打不过 rocksdb 的，因为总是需要拼接 key，如果是大 value，mace 还多了一层 indirection
2. 如果数据都在磁盘上，rocksdb 则打不过 mace，因为 rocksdb 同样有 key 拼接和大 value 的 indirection，并且 rocksdb 需要扫描多个 sst
3. 如果是日常使用 rocksdb 也打不过 mace，因为 rocksdb 从设计上就要求 memtable 变 immemtable 然后刷盘成 sst，因此不可能存在太多的 memtable（毕竟要考虑异常崩溃），尤其是随着数据量越来越大，memtable 的数据的占比会越来越小。如果 rocksdb 设置 table option 的 use_delta_encoding = false 并设置 read option 的 pin_data = true 同样打不过 mace，原因同第二点