数据库索引的排序字符串表(SSTable)或B +树？

Question

使用两个数据库来说明这个例子:CouchDB和Cassandra.

CouchDB的

CouchDB使用B + Tree作为文档索引(使用巧妙的修改在其仅附加环境中工作) - 更具体地说,当文档被修改(插入/更新/删除)时,它们被附加到正在运行的数据库文件以及完整的Leaf - >文档后面的更新版本对受影响的所有节点的B +树的节点路径.

这些分段修改的索引修订与修改一起内联,使得完整索引是附加在文件末尾的最新索引修改的联合,以及在数据文件中进一步返回的仍然相关的附加部分,并且尚未修改.

搜索B +树是O(logn).

卡桑德拉

Cassandra将记录键在内存中保存在表中(让我们将它们视为此问题的数组),并将它们作为单独的(已排序的)排序字符串表不时写出来.

我们可以将所有这些表的集合视为"索引"(根据我的理解).

Cassandra需要不时地压缩/组合这些排序字符串表,从而创建索引的更完整的文件表示.

搜索已排序的数组是O(logn).

题

假设在CouchDB中维护部分B +树块与Cassandra中的部分排序字符串索引之间存在类似的复杂程度,并且假设两者都提供O(logn)搜索时间,您认为哪一个可以更好地表示数据库索引以及为什么？

我特别好奇是否有一个关于一个的实现细节使它特别有吸引力,或者如果它们都是一个清洗,你只需选择你喜欢使用的数据结构/对开发人员更有意义.

谢谢你的想法.

Answer 1

在将BTree索引与SSTable索引进行比较时,您应该考虑写入复杂性:

• 当随机写入写入时复制BTree时,您将产生随机读取(执行叶节点和路径的复制).因此,虽然写入顺序在磁盘上,但对于大于RAM的数据集,这些随机读取将很快成为瓶颈.对于类似SSTable的索引,写入时不会发生此类读取 - 只会进行顺序写入.

• 您还应该考虑在更糟糕的情况下,对BTree的每次更新都可能产生log_b N IO - 也就是说,您最终可能会为每个密钥写入3或4个块.如果密钥大小远小于块大小,则这非常昂贵.对于类似SSTable的索引,每个写入IO将包含尽可能多的新密钥,因此每个密钥的IO成本更像是1/B.

在实践中,这使得SSTable比BTrees快数千倍(对于随机写入).

在考虑实现细节时,我们发现实现类似SSTable的索引(几乎)无锁是更容易的,因为BTrees的锁定策略变得非常复杂.

您还应该重新考虑您的阅读费用.对于随机点读取,你是正确的,而不是BTree是O(log_b N)随机IO,但是类似SSTable的索引实际上是O(#sstables.log_b N).如果没有合适的合并方案,#sstables与N成正比.有各种各样的技巧可以解决这个问题(例如使用布隆过滤器),但这些对小型随机范围查询没有帮助.这就是我们在Cassandra中发现的:

http://www.acunu.com/blogs/richard-low/cassandra-under-heavy-write-load-part-ii/

这就是为什么Castle,我们的(GPL)存储引擎确实合并稍有不同,并且可以实现更好的(O(log ^ 2 N))范围查询性能与写入性能的轻微折衷(O(log ^ 2 N)/B)).在实践中,我们发现它比Cassandra的SSTable写入索引更快.

如果您想了解更多相关信息,我已经谈过它的工作原理:

• http://skillsmatter.com/podcast/nosql/castle-big-data
• http://www.slideshare.net/acunu/in-the-brain-of-tom-wilkie

Answer 2

我认为Tokutek使用的分形树是数据库的更好索引.与b树相比,它们提供了20到80倍的实际改进.

关于分形树索引如何在这里工作有很好的解释.

Answer 3

关于每种方法还应该提到的一些事情：

B树

• 读/写操作应该是对数的O(logn)。但是，单个数据库写入可能会导致存储系统中的多个写入。例如，当一个节点已满时，它必须被拆分，这意味着 2 个新节点将有 2 次写入，而父节点将有 1 次额外写入。如果父节点也已满，您可以看到它会如何增加。
• 通常，B 树以每个节点具有页面大小的方式存储。这会产生一种称为写入放大的现象，即使需要更新单个字节，也会写入整个页面。
• 写入通常是随机的（不是顺序的），因此速度较慢，尤其是磁盘。

SSTables

• SSTables 通常用于以下方法。正如您所描述的，有一个内存结构，称为 memtable。每隔一段时间，这个结构就会刷新到磁盘到一个 SSTable。结果，所有写入都转到内存表，但读取可能不在当前内存表中，在这种情况下，它们会在持久化的 SSTable 中搜索。
• 因此，写入是O(logn). 但是，请始终记住它们是在内存中完成的，因此它们应该比 B 树磁盘中的对数运算快几个数量级。为了完整起见，我们应该提到写入也写入预写日志以进行崩溃恢复。但是，鉴于这些都是顺序写入，预计它们比 B 树的随机写入效率更高。
• 当从内存（来自 memtable）提供服务时，预计读取速度也会快得多。但是，当需要查看旧的、基于磁盘的 SSTable 时，读取可能会变得比 B 树慢得多。围绕它有几个优化，例如使用布隆过滤器，以检查 SSTable 是否包含值而不执行磁盘读取。
• 正如您提到的，还有一个后台进程，称为compaction，用于合并 SSTables。这有助于删除已删除的值并防止碎片化，但它可能会导致大量写入负载，从而影响传入操作的写入吞吐量。

很明显，这两种方法之间的比较要复杂得多。在提供具体比较的极其简化的尝试中，我认为我们可以说：

• SSTables 提供比 B-trees 更好的写入吞吐量。然而，由于持续的压缩，预计它们的行为不太稳定。在这个基准比较中可以看到一个例子。
• B 树通常首选用于需要事务语义的用例。这是因为，每个键只能在一个地方找到（与 SSTable 相反，它可以存在于多个 SSTable 中，其中一些值已经过时），而且还因为一个可以表示一系列值作为树。这意味着更容易执行键级和范围级锁定机制。

参考

[1] LevelDB和MySQL的性能比较

[2]设计数据密集型应用程序