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

Question

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

CouchDB

CouchDB 使用 B+ 树作为文档索引(使用 a clever modification 在其仅附加环境中工作)——更具体地说，当文档被修改(插入/更新/删除)时，它们被附加到正在运行的数据库文件以及一个完整的 Leaf -> Node 路径，来自 B+ 树的所有节点，这些节点在文档之后立即受到更新修订的影响。

这些零碎的索引修订与修改一起内联，这样完整的索引是附加在文件末尾的最新索引修改以及数据文件中仍然相关的其他部分的联合并且还没有被修改。

Searching the B+ tree is O(logn).

Cassandra

Cassandra 在内存中和表中对记录键进行排序(让我们将它们视为这个问题的数组)并将它们作为单独的(排序的)写出 sorted-string tables不时。

我们可以把所有这些表的集合看作是“索引”(据我理解)。

Cassandra 需要 compact/combine these sorted-string tables不时创建更完整的索引文件表示。

Searching a sorted array is O(logn).

问题

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

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

谢谢你的想法。

Answer 1

在比较 BTree 索引和 SSTable 索引时，您应该考虑写入复杂度:

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

• 您还应该考虑到，在最坏的情况下，对 BTree 的每次更新都可能引发 log_b N 次 IO - 也就是说，您最终可能会为每个键写入 3 或 4 个 block 。如果 key 大小远小于 block 大小，这将非常昂贵。对于类似 SSTable 的索引，每个写入 IO 将包含尽可能多的新键，因此每个键的 IO 成本更接近 1/B。

在实践中，这使得类似 SSTable 的速度(对于随机写入)比 BTree 快数千倍。

在考虑实现细节时，我们发现实现类似 SSTable 的索引(几乎)无锁要容易得多，而 B 树的锁定策略变得相当复杂。

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

Cassandra under heavy write load

这就是为什么我们的 (GPL) 存储引擎 CaSTLe 在合并时略有不同，并且可以实现更好的 (O(log^2 N)) 范围查询性能，同时略微牺牲写入性能 (O(log ^2 N/B))。在实践中，我们发现它在写入方面也比 Cassandra 的 SSTable 索引更快。

如果您想了解更多，我已经讲过它是如何工作的:

• podcast
• slides