针对google的文章How Index Building Works进行了翻译，在读这篇文章的时候最好先了解Bigtable的相关内容，可以参看“大表(Bigtable):结构化数据的分布存储系统”。
每一个GAE应用都是依据索引进行查询，内置的索引可以处理简单的查询，包括在单个属性上的指定类型，过滤和排序，以及在很多属性上的“等于”过滤。更复杂的查询，需要定制developer-defined indexes
实际上，我们叫它为组合索引，以别于内在类型和单个属性的索引。我们这样说是因为这些索引数据是由每个索引列的多个值组成。
当你在应用中添加一个组合索引时，必须把你已经存在的数据填充到索引中，这时候的索引才能提供查询服务。同样，当删除一个索引时，索引列必须被删除。GAE在后台运行索引构建流程进行索引的填充和删除。
本文描述了索引如何排列，索引创建流程，以及常见问题。
索引排列
索引数据存储在四个bigtables中，被所有应用共享。前三个表存储内在类型，单个属性的升序，降序索引数据，最后一个表存储组合索引数据。
索引列的索引数据存储在bigtables的列名称中，包括app id, kind, key以及索引中额外的数据。内置的单个属性索引的额外数据包括属性名和值，内置的类型索引则没有额外数据。
组合索引中的额外数据包含了在索引定义中各个属性的值，如果指定了祖先的话，则包含祖先。属性名称省略，可以节约空间，因为索引定义中已经包含了属性名称。但是，组合索引列中包含了一个索引id，用来区分不同的组合索引恰好在同样的顺序下具有同样的属性值。
欲了解更多关于索引排列，请看Google I/O 下描述的Under the Covers of the Google App Engine Datastore。
索引创建和删除
当你定义好一项新的索引，并要求我们创建时，我们按照下列步骤进行：
- 增加索引定义到应用中。
- 标识索引正在构建（Building），这样就告诉了数据存储，需要更新所有的写入，但是还不能用它进行查询。
- 映射存在的实体，将其填充到索引中。
- 标识索引正在服务（Serving），这样该索引就可以用于查询了。
删除索引几乎是相同的过程：
- 标识索引正在删除（Deleting），这样告诉数据存储，忽略该索引的查询和写入
- 删除索引列
- 删除索引的定义
当一个实体创建或删除，所有和该实体相关的索引列必须更新。但是，当一个实体更新时，如某些属性改变了，则仅仅更新和这些属性相关的索引。
另外，这些组合索引的处理是自动的。当一个实体需要保存或者删除，数据存储系统根据上面的规则找到相关索引，并进行更新。
由于索引更新的高效和自动化，索引构建流程可以简单重复的使用。要建立或者删除索引，流程会映射一次应用所有的实体。对于每个实体，流程使用数据存储系统在一个事务中进行读，写，保持不变。数据存储系统检测Building和Deleting状态的索引，更新相关的索引列。
并行工作
索引构建流程在并行地渐进建立和删除索引，这样可以使不同应用的索引可以在同一时间创建和删除。也可以让同一个应用里面的不同索引同时创建或者删除。最后，如果流程当掉之后，可以设立检查点恢复工作。
工作流程保存了一份在所有应用中将要删除或建立的索引列表。每一个应用的数据分成了多个碎片（shards）。当一个工作器空闲时，它查询这个列表，借用一份碎片的数据，映射碎片中的实体，象上面所说的那样填充索引列。如果在借用期到了，工作器还没有做完，则工作器放弃工作，丢弃部分完成的工作。该碎片（shards）可以再被其他工作器使用。
我们已经实现了几个不同的碎片数据机制：首先是Bigtable tablet,其次是在tablets内部，这两种方法说明如下。
以tablet进行分割
令人惊讶的是，分割一个应用的实体成为碎片不是很容易的。最理想的情况是，工作流程每N列询问一次Bigtable，从应用的第一个实体开始，到最后一个实体结束。这些将是分割点，用以区分每一份碎片。
然而，Bigtable并不打算提供这样的操作方式。于是我们提供了一个近似的方法，Bigtable按照相临的列把数据进行分块，这些块叫做tablet，它能够在运行的时候在不同的tablet服务器上进行分割，合并，移动等。Bigtable知道tablet的开始和结束列，所以我们把每一个tablet标为一个碎片（shard）。
不幸的是，tablet受限制于数据大小，所以列（实体）的数目在不同的tablet中是不同的。填充索引数据的时间更多依赖于实体的属性数目，而不是实体大小，所以不同的tablet 碎片花费的时间完全不同。在具有很多列的tablet中，工作器经常超过它的借用期，索引的删除(deleting)或者创建(building)状态会保持很长时间。
在tablets内进行分割
为了解决上述问题，我们最近增加了大碎片（shard）的分割功能。当一个工作器发现它在一块碎片上的借用期即将到期的时候，它放弃这个工作，将碎片分割成n个小碎片，每一个小碎片包含了原始碎片的列范围和两个碎片参数：n，每小片都相同。k，从0到n-1的范围。
当一个工作器取走带有分割参数的碎片时，它映射到碎片列范围中的所有实体，通常，它会列举每一个实体，计算实体key的hash值，仅仅当实体的hash值等于k%n时，它才填充索引。
交替设计可以用于填充每k个实体，这样变得很简单。但是有可能会遗漏某些实体，因为在这个处理过程中，应用可能会增加或者删除实体。
必须强调的是，在分割的时候，碎片的列范围是不会改变的。工作器依然扫描列范围内所有的实体，这个扫描相对于读写索引来说是很便宜的。进一步说，磁盘的大小比磁盘定位要便宜很多。所以Bigtable扫描比随机访问一个特定的列进行读写要便宜很多。
FAQs
下面是关于一些索引创建和删除的常规问题（如果你比较好奇怎样给你的应用指定索引，可以访问我们的文档）
Q.为什么我的索引保持Building或Deleting状态那么长的时间？
A.在过去，通常是工作器中的碎片太大，以至于在碎片的借用期内无法完成。为了解决这个问题，我们首先增加了借用期限，现在我们可以将tablet分割成碎片，索引创建仍然需要一点时间，但是现在比以前快了许多。
Q.为什么我的索引标为Error状态？
A.大概是exploding indexes（爆炸索引），有时候，我们不得不手工标记索