在GAE查询中如何实现filter()和get()？

Question

我基本上想知道GAE是如何实现它的索引的，我熟悉像B+树这样的索引，我想知道，例如，filter()方法是不是使用B+树来实现它？我可以在SDK的appengine代码中看到这个实现吗，因为它是开源的？get()和get_by_id()函数是否使用散列实现为O(1)`过滤函数是O( B+ (N))，因为人们可能认为它使用的是log树，其中查找是O(log(n))？

感谢你的见解

Answer 1

长长的答案是我几年前的演讲：Under the Covers of the Google App Engine Datastore。您还会对Bigtable paper和Megastore paper感兴趣。

简而言之，查询过滤是通过单属性和多属性(也称为复合)索引来实现的。查询规划器选择一个或多个进行密集扫描和合并，即所有或几乎所有扫描的索引行都对应于查询的有效结果。细节在我的演讲中。

get()被实现为bigtable单行查找。它介于O(1)和O( log(n) )之间，具有较小的恒定因子，因为log(N)部分通常完全在内存中发生。bigtable论文中的详细信息。