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