问题标签 [lsm-tree]

对于简单的搜索查询（例如查询单个WHERE子句），日志结构合并树的最坏情况时间复杂度是多少？

是 O(log N) 吗？O(N*Log N)？还有什么？

WHERE多查询怎么样，比如在键值数据库中 搜索多个子句？

LSM 树上的维基百科页面目前缺少此信息。

我正在尝试理解原始论文。

LSM 树已在许多 no-sql 引擎中成功使用，它的数据按键排序，不像散列表，因此可以在 kv 存储之外实现许多潜在用途。例如，时间序列数据库 (TSDB) 可能非常适合使用级别 db 作为其引擎。传统的 RDBMS 和许多表系统怎么样？像 LSM-tree 这样的数据引擎也很合适吗？

在使用 RocksDB 中的 HASHSKIPLIST 内存表进行批量插入期间，我无法触发压缩。我使用 PlainTable SST 文件格式。Memtable 大小设置为 64MB，写入缓冲区数为 6。在插入 200Million 数据时，level0 文件的数量约为 80+，我没有看到压缩被触发。我已经将level0配置如下，

level0_stop_writes_trigger=36

level0_slowdown_writes_trigger=20

level0_file_num_compaction_trigger=2

如果我将 memtable 设置为 SKIPLIST，我可以看到压缩。我不确定是什么阻止了 HashSkiplist 中的压缩。怎么触发？？提前致谢。

上下文：我正在阅读有关 RocksDB 和 LSM 树的信息，据我了解，Bloom 过滤器用于避免在所有存储级别中检索多个 I/O。我同意。

显然，挑战之一是布隆过滤器不能用于范围查询。是什么原因？如果我想检查 32 到 200 之间是否有一个键，我可以对中间的每个值进行单键查找（或在第一个“真”响应处停止）。真的没有效率吗？

LSM树为什么叫索引结构？我的理解是它们是一种“存储技术”，即您如何在下面存储数据。

事实上，出于性能原因，您需要在此数据之上建立一个索引——在 LSM 的这种情况下，一个内存哈希映射或一个块索引——以快速定位您想要的数据。

我知道您可以在内部将索引内容存储为 LSM 树，但几乎所有我读过的 LSM 树都被称为索引结构。我觉得这很混乱，怀疑我的概念是否正确？

谢谢

根据官方文档，LevelDB中的lower level是upper one的10倍，这是毫无疑问的。

问题是为什么是10？不是2？不是20？这是由于一些严格的数学计算还是它只是有效？

我已经阅读了原始的LSMT 论文。我可以理解多组件部分，因为将 c0 树与超大 c1 树合并太难了。但是该论文没有显示最佳参数是什么。

我对吗？这实际上是一个面试问题。如果没有最佳参数，我该如何正确回答？

最近一直在研究数据库中常见的索引结构，比如B+-trees和LSM。我对点读/写/删除/压缩如何在 LSM 中工作有一个可靠的处理。

例如（在 RocksDB/levelDB 中），在点查询读取时，我们将首先检查内存中的索引（memtable），然后是从最近到最近的一些 SST 文件。在 LSM 的每个级别上，我们将使用二进制搜索来帮助加快查找给定键的每个 SST 文件。对于给定的 SST 文件，我们可以使用布隆过滤器快速检查密钥是否存在，从而节省更多时间。

我没有看到范围读取具体是如何工作的。LSM 是否必须在每个 SST 级别（包括内存表）上打开一个迭代器，并在所有级别上同步迭代，以返回最终排序结果？它是否仅作为一系列点查询实现（几乎肯定不是）。是否所有潜在的键都先被拉出，然后再排序？将不胜感激有人在这里有任何见解。

我无法找到有关该主题的太多文档，任何见解都会在这里有所帮助。

Google BigTable 是一个使用 LSM-tree 作为其核心数据结构进行存储的系统。LSM-tree 可以使用不同的合并策略。最常见的两个是（1）更读优化的水平合并，和（2）更写优化的分层合并。这些合并策略可以通过调整相邻级别之间的大小比来进一步配置。

我无法在任何地方找到 BigTable 在这些方面的默认行为，以及是否可以对其进行调整。因此，很难理解它的默认性能属性以及如何使它们适应不同的工作负载。

通过分层合并，一层 LSM-tree 集合会一直运行，直到达到容量为止。然后它合并这些运行并将生成的运行刷新到下一个更大的级别。每个级别最多运行O(T * log_T(N))，写入成本为O(log_T(N) / B)，其中N是数据大小，B是块大小，T是大小级别之间的比率。

使用分级合并，LSM-tree 的每一级都有一个运行。一旦新的运行进入级别，就会发生合并，如果级别超过容量，则生成的运行将被刷新到下一个更大的级别。每个级别最多运行 O(log_T(N)) 次，写入成本为 O((T * log_T(N)) / B)。

因此，这些方案具有不同的读/写性能属性。但是，我一直无法找到有关 Google 的 BigTable 是使用分级合并还是分层合并的来源，以及默认大小比 T 是多少？另外，系统的这些方面是固定的，还是可调的？

例如，我向 DB 添加了几个键，例如，

首先Seek()到 <1, 2> 然后Next()到 <1, 3> 之后，我想跳过键 <2, 1> 和 <2, 4> （它们的前缀都是2）并将迭代器移动到 <3, 2>无需新seek操作。使用新Seek()操作是出乎意料的，因为它Seek()是昂贵的。我应该使用哪种方法？

这种跳过扫描方法与此类似

我更喜欢像下面这样编程：

Are these two terms used interchangeably?

I have read about how SSTable works, and usually, articles just start mentioning LSM Tree. However, they seem to be the same thing.

When should I use one term over the other?