bigtable - Google BigTable 是否支持范围扫描？
问题描述
我是学习 Google BigTable 设计的学生。
我很困惑，SST 表是内部排序的。两个 SST 表可能没有排序。在这种情况下，BigTable 似乎不支持对主键进行有效范围扫描？例如，“select * where id 介于 100 和 200 之间”。BigTable 可能需要扫描所有的 SST 才能得到结果。
那么我对为什么要对 SST 进行排序的理解是因为对于单主键查询，我们可以在 SST 中进行二进制搜索。
我的另一个问题是，MemTable 是否已排序？如果是，如何？因为 MemTable 需要经常更新。如果使用树这样的数据结构，那么我们在将 MemTable 写入 SST 时需要遍历树吗？
解决方案
听起来您至少已经阅读了原始 Bigtable 论文的概述，但是如果您还没有阅读整篇文章，这里是一个参考；您的问题大多可以通过仔细阅读来回答：https ://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf
你对 Bigtable 的直觉是正确的。磁盘上的 SStables 和 Memtable 都是基于主键排序的，任何读取（不仅仅是扫描）都需要查阅它们以生成合并视图。但是，请注意，它们都按相同的键排序，因此这相当于并行遍历。我们在每个 sstable 和 memtable 中寻找要读取的范围的开头，并从那里并行遍历它们。
这个过程在 5.3 节中提到：“在 SSTables 和 memtable 的序列的合并视图上执行有效的读取操作。由于 SSTables 和 memtable 是按字典顺序排序的数据结构，因此可以有效地形成合并视图。”
如本文第 6 节所述，可以使用 Bloom Filters 减轻其中一些查找，但不是全部。
当然，如果平板电脑中的 sstables 太多，这仍然会变得低效。论文的第 5.4 节更详细地介绍了如何解决这个问题，即定期将平板电脑的 sstables“堆栈”合并到较少数量的新 sstables 中。如果特定的 tablet 停止接收写入，这最终会将其状态静默到单个文件。
关于memtable的效率，论文没有规定特定的数据结构。然而，只要说有很多高效的内存排序数据结构的例子就足够了。此外，第 5.4 节提到在给定的 tablet 中实际上可以有多个 memtables。当我们扫描一个 memtable 并将其写入磁盘时，我们已经在 tablet“stack”的顶部安装了一个新的 memtable，并从那里提供最新的传入读取。