我基本上想知道 GAE 是如何实现它的索引的，我熟悉诸如 B+ 树之类的索引，并且想知道 filter() 方法是否使用 B+ 树来实现它？我可以在 SDK 的 appengine 代码中看到这个实现，因为它是开源的吗？get() 和 get_by_id() 函数是否使用散列实现 O(1)`是过滤函数 O(log(n))，因为有人可能认为它使用 B+ 树，其中查找为 O(log(n) )?
感谢您的任何见解
问问题
92 次
1 回答
5
长长的答案是我几年前的演讲：在 Google App Engine Datastore 的掩护下。您还会对Bigtable 论文和Megastore 论文感兴趣。
简短的回答是，查询过滤是通过单属性和多属性（又名复合）索引实现的。查询计划器选择一个或多个进行密集扫描和合并，即所有或几乎所有扫描的索引行都对应于查询的有效结果。我的谈话中的细节。
get() 被实现为一个大表单行查找。它介于 O(1) 和 O(log(n)) 之间，常数因子很小，因为 log(n) 部分通常完全发生在内存中。bigtable 论文中的详细信息。
于 2012-05-16T19:44:15.527 回答