如何在GAE查詢中實現filter（）和get（）？

Question

我基本上想知道GAE如何實現它的索引，我熟悉索引如B +樹和不知道是否例如。 filter（）方法使用B +樹來實現它？因爲它是開源的，我可以在SDK的appengine代碼中看到這個實現嗎？使用散列實現get（）和get_by_id（）函數使其成爲O（1）`是過濾函數O（log（n）），因爲人們可能認爲它使用B +樹，其中查找是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文件中的細節。