在LSM-树中，memtable到底是如何刷新到磁盘上的SSTable的？

Question

就实现而言，memtable (在Cassandra、RocksDB、LevelDB或任何LSM-树中)到底是如何并发到SSTable的？

我了解到，记忆表是一些结构化的排序数据，就像一棵红黑树，但是我们如何将它转换成一个排序的键/值对文件呢？我们是否在for-循环中遍历从最小键到最大树的树，然后一个一个地将数据插入内存缓冲区(以SSTable格式)，然后将其写入磁盘？我们是否使用某种树序列化方法(如果是的话，它如何仍然是SSTable格式的)？我们可以用一个min堆作为memtable吗?在刷新时，继续获取min元素并将其添加到我们的数组中进行刷新吗？

我在试着理解超具体的细节。我在看这个文件，但是很难理解它：https://github.com/facebook/rocksdb/blob/fbfcf5cbcd3b09b6de0924d3c52a744a626135c0/db/flush_job.cc

Answer 1

你是对的。

备忘录被从最小的循环到最大的，并写成文件。

在实际应用中，还有其他东西也写入到文件中，但是文件的基础是包含以前在memtable中的所有键的部分。例如，布卢姆筛选器，查找稀疏索引，以及其他元数据，如计数，最大键，最小键

你不需要一个小矮人。，因为数据已在跳过列表中排序。

Answer 2

RocksDB的默认备忘录表是使用skiplist实现的，它是一个具有二进制搜索功能的链接列表，类似于B+树。当写入SST表时，它按排序顺序迭代所有键。