数据库索引的sortingstring表(SSTable)或B +树?

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

CouchDB的

CouchDB使用一个B +树来处理文档索引(使用一个巧妙的修改在其append-only环境中工作) – 更具体地说,当文档被修改(插入/更新/删除)时,它们被附加到正在运行的数据库文件以及完整的Leaf – >所有节点的B +树节点path,由文档之后的更新版本实现。

这些分片索引修订内容正好与修改一起内联,使得完整索引是在文件末尾附加的最近的索引修改的联合,以及在数据文件中更远的附加部分,这些附加的部分仍然是相关的,尚未修改。

searchB +树是O(logn)。

卡桑德拉

Cassandra将logging键保存在表中(我们把它们看作是这个问题的数组),并将它们作为单独的(sorting的) sortingstring表格不时地写出来。

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

Cassandra需要时常压缩/合并这些sortingstring表 ,创build更完整的索引文件表示。

searchsorting的数组是O(logn)。

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

我特别好奇的是,如果有一个相对于另一个的实现细节,使其特别具有吸引力,或者如果他们都是洗钱,并且您只是select您喜欢使用的任何数据结构/对开发人员更有意义。

谢谢你的想法。

3 Solutions collect form web for “数据库索引的sortingstring表(SSTable)或B +树?”

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

  • 随机写入写入时复制BTree时,将会产生随机读取(执行叶节点和path的副本)。 所以,虽然写我的顺序在磁盘上,对于大于RAM的数据集,这些随机读取将迅速成为瓶颈。 对于类似于SSTable的索引,写入时不会发生这种读取 – 只会有顺序写入。

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

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

在考虑实现的细节时,我们发现实现类似于SSTable的索引(几乎)无locking更容易,其中BTrees的locking策略变得相当复杂。

你也应该重新考虑你的阅读成本。 你是正确的,而BTree是O(log_b N)随机IO读取随机点,但类似于SSTable的索引实际上是O(#sstables。log_b N)。 如果没有合适的合并scheme,#sstables与N成正比。有很多方法可以解决这个问题(例如使用Bloom Filters),但是这些方法对于小型的随机范围查询没有帮助。 这就是我们在Cassandra中发现的:

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

这就是为什么我们的(GPL)存储引擎Castle的合并方式稍有不同,并且在写入性能(O(log ^ 2 N) / B))。 实际上,我们发现它比Cassandra的SSTable索引更快。

如果你想知道更多关于这个,我已经谈了它是如何工作的:

我认为Tokutek使用的分形树是一个更好的数据库索引。 他们提供实际的20倍到80倍的改进。

分形树指数如何在这里工作有很好的解释。

在存储引擎结构上,LSM-Trees比B-Tree要好。 它以某种方式将随机写入转换为aof。 这是一个LSM-Tree src: https : //github.com/shuttler/lsmtree

  • 什么是BSON,和JSON有什么不同?
  • MongoDB不符合ACID标准是什么意思?
  • 有没有JSON的查询语言?
  • 你如何在Mongo中查询这个? (不为空)
  • Firebase中的多对多关系
  • 非关系数据库devise
  • DynamoDB与MongoDB NoSQL
  • MongoDB:如何用一个命令更新多个文档?
  • 从MySQL切换到Cassandra - 优点/缺点?
  • mongodb在CAP定理中站在哪里?
  • 什么types的NoSQL数据库最适合存储分层数据?