• 2. HashLinkList 内存表
  • 2.2. 实现代码
    • 2.2.2. Get

为了方便使用，内存表有对应的工厂类 MemTableRepFactory。与内存表类型对应，完整的内存表工厂类的继承关系如下图：

相比 HashSkipList 而言，HashLinkList 要更简洁/简单一些，也可以节约内存的占用。它的缺点是不支持并发的写入。为了测试各种内存表的表现，RocksDB 提供了一个简单的测试工具，参看：memtablerep_bench.cc。我们也可以在示例代码 examples/simple_example.cc 中修改一下来验证 HashLinkList 的使用。例如：

需要注意的几个地方：

1. options.memtable_factory.reset() 是将默认的 SkipList 替换为我们要测试的 HashLinkList。
2. options.prefix_extractor.reset() 是设置 Hash 需要的 prefix_extractor，如果不设置，默认用的还会是 SkipList。
3. options.allow_concurrent_memtable_write = false 是因为 HashLinkList 不支持并发写入，不设置运行时会报错。
4. 数据存放在 /tmp/rocksdb_simple_example，如果数据目录已经存在，则会打开已经存在的数据库。

实现代码

HashLinkList 的代码存在以下两个文件中：memtable/hash_linklist_rep.h 以及 memtable/hash_linklist_rep.cc。可以看到它做了一些细节的优化，从简单的 Hash 链表逐步演化到 Hash 跳表。代码注释得非常清楚，参看下图：

由于存在上述的一些优化，Hash 表在不同时刻会存在不同的形式。

1. 第一种情况最简单，也就是桶为空。不占用额外内存空间。
2. 第二种情况下，桶里头只有一条记录，存在链表第一个节点中。Next 指针占用额外空间。Next 指针取值为 NULL。后续其他情况下 Next 指针都不是 NULL，可以依赖这一点来区分不同的场景。
3. 第四种情况下，桶里头的记录数超过了设定的阈值（threshold_use_skiplist），链表被转换为一个跳表。链表的第一个节点的 Next 指针指向自己。Count 继续保留，可以用来做测试等。

如果 HashLinkList 要支持并发写，就需要对数据结构做适当的控制。不过当前它并不支持并发写，而是单写多读。它实现时采用了 C++ 11 的 Atomic 做一些特殊的处理避免加锁。另外需要注意的是，这个 Iterator 的实现 MemTableRep::Iterator* HashLinkListRep::GetIterator() 比较费资源，它会 new 一个 MemtableSkipList，把记录都遍历出来并插入进去。

采用修改后的 simple_example.cc，可以看到插入、查找、删除所对应的执行路径，用来理解代码的主要执行流程。

Put

Get

Delete