database是按uuid auto increase的int作为primary key。搜pk肯定不需要o(N)全表遍历，至少可以二分o(logn).
但有时候想搜某一性质的内容。比如姓名，比如车型，这样。遍历全表会很慢，如果是搜索频率比较高的性质，可以考虑做index，变成o(1) (hashmap) 或 o(logn), 提升搜索速度。
关系型数据库里，只要create index就好.
非关系型数据呢？
两种方法 1、Local Index对每一个partition, 增加一个关于index的hashmap，这里用最简单的hash index为例子，key是想作index的那一类，比如员工姓/姓名，value是list of Primary Key、比如：
王：1， 5， 7， 99， 。。
李：2， 12， 。。。
张明：108，222， 。。。
这样每一个partition都维护一个自己的hashmap。
写每在一个partition里写一个新数据，都在该partition的hashmap里相关index后面加上这个新pk。快
读那么如果我们想搜王姓员工，就要遍历(scatter)每一个partition 的hashmap, 拿到每一个的王姓的结果，再合在一起(gather)。慢
应用cassendra，mongoDB
2、Global Index单独维护关于index的hashmap，和数据可以不在一个partition, 所有partition的数据共用一个hashmap (即global的index）。故只有一个王姓的key，所有结果都加在该key后面。
写每在一个partition里写一个新数据，就在global hashmap里面相关的tag后面加上这个数据的pk。因为可能有很多相关index，且相关index可能不在同一Partition，所以慢。往往offline 异步进行。
读只需要去global hashmap里面读一次，就是所有王姓的结果。快。
应用DynamoDB，craigslist