数据库索引的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您喜欢使用的任何数据结构/对开发人员更有意义。
谢谢你的想法。
将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
