10.6 用索引提高性能

    高效的规则之一是避免搜索。我们前面展示的一个遍历shelf上所有键的例子是非常低效的。更具强调性的说法是，搜索意味着低效。我们会在这个部分中着重探讨这点。

    穷举搜索可能是处理时最糟糕的方法，我们必须总是基于数据的子集或者映射创建索引以提高性能。

    为了避免搜索，我们需要基于被搜索的元素创建索引。有了这些索引之后查询某个元素或者某些元素时就不用遍历整个shelf。shelf的索引不能引用Python对象，因为这会改变对象存储的粒度。shelf索引只能基于键。这使得不同对象间的跳转变得不直接，但是仍然比遍历shelf上所有元素的穷举搜索要快很多。

    索引的一个例子是可以用一个列表保存与shelf上的Blog相关的所有Post的键，也可以很轻易地通过修改add_blog()、add_post()和delete_post()方法来更新相关的Blog对象。下面这些代码是博客更新方法的修订版本。

    class Access2( Access ):
    　　def add_blog( self, blog ):
    　　　　self.max['Blog'] += 1
    　　　　key= "Blog:{id}".format(id=self.max['Blog'])
    　　　　blog._id= key
    　　　　    blog._post_list= []
    　　　　self.database[blog._id]= blog
    　　　　return blog
    　　def add_post( self, blog, post ):
    　　　　self.max['Post'] += 1
    　　　　try:
    　　　　　　key= "{blog}:Post:{id}".format(blog=blog._id,id=self.
    max['Post'])
    　　　　except AttributeError:
    　　　　　　raise OperationError( "Blog not added" )
    　　　　post._id= key
    　　　　post._blog= blog._id
    　　　　self.database[post._id]= post
    　　　　    blog._post_list.append( post._id )
    　　　　    self.database[blog._id]= blog
    　　　　return post
    　　def delete_post( self, post ):
    　　　　del self.database[post._id]
    　　　　blog= self.database[blog._id]
    　　　　    blog._post_list.remove( post._id )
    　　　　    self.database[blog._id]= blog
    addblog()方法确保每个Blog都有一个额外的postlist属性。其他的方法会用这个属性维护一个属于当前Blog的所有Post的键的列表。注意我们不是将Posts本身添加到列表中，如果添加了Posts本身，那么就是将整个Blog保存在shelf上的单一对象中。通过只添加键，让Blog和Post对象保持独立。 add_post()方法将Post添加到shelf上。它也会将Post._id添加到Blog中维护的键列表中。这意味着任何Blog对象都会有一个用于提供所有子Post对象键的_post_list属性。 这个方法更新了shelf两次。第1次只是简单地保存了Post对象。第2次的更新至关重要，我们没有尝试简单地修改shelf上的Blog对象，更倾向于确保保存到shelf上的对象都是最新的。 类似地，delete_post()方法通过将不再使用的Post索引从所属Blog对象的_post_list中移除来保证索引是最新的。和add_post()类似，这个方法也更新了shelf两次：del语句删除Post，然后更新Blog对象以反映索引的改变。 这些修改彻底改变了查询Post对象的方式，下面是搜索方法的修订版本。
    def __iter( self ):
    　　for k in self.database:
    　　　　if k[0] == "    ": continue
    　　　　yield self.database[k]
    def blog_iter( self ):
    　　for k in self.database:
    　　　　if not k.startswith("Blog:"): continue
    　　　　if ":Post:" in k: continue # Skip children
    　　　　yield self.database[k]
    def post_iter( self, blog ):
    　　    for k in blog._post_list:
    　　    　　yield self.database[k]
    def title_iter( self, blog, title ):
    　　return ( p for p in self.post_iter(blog) if p.title == title )
    我们将post_iter()中的扫描替换成了一个高效得多的操作，这个循环会基于Blog的_post_list属性中存储的键快速地返回Post对象，我们可以考虑将for语句替换为一个生成器表达式。
    return (self.database[k] for k in blog._post_list)
    post_iter()方法的这个优化方式的目的是避免搜索所有的键。我们将搜索所有的键替换成了简单适当地迭代一些相关的键。下面是一个简单的性能测试的结果，我们交替地更新Blog和Post并且将Blog转换为RST标记。
    Access2: 14.9
    Access: 19.3

    和预期的一样，避免搜索从而减少了处理Blog和每个Posts所需要的时间。这个改变是非常重要的，处理时间中几乎有25%的时间都浪费在搜索上。

    创建顶层索引

    我们在每个Blog中增加了一个用于定位所有相关Posts的索引。我们也可以在shelf上添加一个用于定位所有Blog实例的顶层索引。基本的设计方法和前面看到的大体一致。对每一个被添加或者删除的Blog，我们必须要更新索引的结构。为了能够正确地迭代，还必须修改迭代器。下面是间接访问对象的另一种设计。

    class Access3( Access2 ):
    　　def new( self, args, **kw ):
    　　　　super().new(     args, **kw )
    　　　　    self.database['_DB:Blog']= list()

    　　def add_blog( self, blog ):
    　　　　self.max['Blog'] += 1
    　　　　key= "Blog:{id}".format(id=self.max['Blog'])
    　　　　blog._id= key
    　　　　blog._post_list= []
    　　　　self.database[blog._id]= blog
    　　　　    self.database['_DB:Blog'].append( blog._id )
    　　　　return blog

    　　    def blog_iter( self ):
    　　    　　return ( self.database[k] for k in self.database['_DB:Blog'] )

    在创建数据库时，添加了一个管理对象以及值为“_DB:Blog”的索引。这个索引列表将用来存储每个Blog对象的键值。当添加一个新的Blog对象时，也会使用修改的键值列表来相应地更新“_DB:Blog”对象的值。此处没有演示删除的实现，因为这部分逻辑很直接。

    当对Blog对象中的文章进行迭代时，使用了索引列表来替代直接在数据库中使用关键字进行搜索。以下是一些性能测试的数据：

    Access3: 4.0
    Access2: 15.1
    Access: 19.4

    从以上结果中可以得出绪论，大部分时间浪费在了使用关键字直接对数据库进行搜索的过程中。在程序的性能优化过程中，首先应该要考虑到的就是尽量避免使用关键字对数据库进行直接搜索。