是什么影响数据检索效率

　　数据检索有两种主要形态。第一种是纯数据库型的。典型的结构是一个关系型数据，比如 MySQL。用户通过 SQL 表达出所需要的数据，mysql 把 SQL 翻译成物理的数据检索动作返回结果。第二种形态是现在越来越流行的大数据玩家的玩法。典型的结构是有一个分区的数据存储，最初这种存储就是原始的 HDFS，后来开逐步有人在 HDFS 上加上索引的支持，或者干脆用 Elasticsearc 这样的数据存储。然后在存储之上有一个分布式的实时计算层，比如 Hive 或者 Spark SQL。用户用 Hive SQL 提交给计算层，计算层从存储里拉取出数据，进行计算之后返回给用户。这种大数据的玩法起初是因为 SQL 有很多 ad-hoc 查询是满足不了的，干脆让用户自己写 map/reduce 想怎么算都可以了。但是后来玩大了之后，越来越多的人觉得这些 Hive 之类的方案查询效率怎么那么低下啊。于是一个又一个项目开始去优化这些大数据计算框架的查询性能。这些优化手段和经典的数据库优化到今天的手段是没有什么两样的，很多公司打着搞计算引擎的旗号干着重新发明数据库的活。所以，回归本质，影响数据检索效率的就那么几个因素。不妨让课课家带你来看一看。

　　数据检索干的是什么事情

　　定位 => 加载 => 变换

　　找到所需要的数据，把数据从远程或者磁盘加载到内存中。按照规则进行变换，比如按某个字段group by，取另外一个字段的sum之类的计算。

　　影响效率的四个因素

　　读取更少的数据

　　数据本地化，充分遵循底层硬件的限制设计

　　更多的机器

　　更高效率的计算和计算的物理实现

　　原则上的四点描述是非常抽象的。我们具体来看这些点映射到实际的数据库中都是一些什么样的优化措施。

　　读取更少的数据

　　数据越少，检索需要的时间当然越少了。在考虑所有技术手段之前，最有效果的恐怕是从业务的角度审视一下我们是否需要从那么多的数据中检索出结果来。有没有可能用更少的数据达到同样的效果。减少的数据量的两个手段，聚合和抽样。如果在入库之前把数据就做了聚合或者抽样，是不是可以极大地减少查询所需要的时间，同时效果上并无多少差异呢?极端情况下，如果需要的是一天的总访问量，比如有1个亿。查询的时候去数1亿行肯定快不了。但是如果统计好了一天的总访问量，查询的时候只需要取得一条记录就可以知道今天有1个亿的人访问了。

　　索引是一种非常常见的减少数据读取量的策略了。一般的按行存储的关系型数据库都会有一个主键。用这个主键可以非常快速的查找到对应的行。KV存储也是这样，按照Key可以快速地找到对应的Value。可以理解为一个Hashmap。但是一旦查询的时候不是用主键，而是另外一个字段。那么最糟糕的情况就是进行一次全表的扫描了，也就是把所有的数据都读取出来，然后看要的数据到底在哪里，这就不可能快了。减少数据读取量的最佳方案就是，建立一个类似字典一样的查找表，当我们找 username=wentao 的时候，可以列举出所有有 wentao 作为用户名的行的主键。然后拿这些主键去行存储(就是那个hashmap)里捞数据，就一捞一个准了。

　　谈到索引就不得不谈一下一个查询使用了两个字段，如何使用两个索引的问题。mysql的行为可以代表大部分主流数据库的处理方式：

　　基本上来说，经验表明有多个单字段的索引，最后数据库会选一最优的来使用。其余字段的过滤仍然是通过数据读取到内存之后，用predicate去判断的。也就是无法减少数据的读取量。

　　在这个方面基于inverted index的数据就非常有特点。一个是Elasticsearch为代表的lucene系的数据库。另外一个是新锐的druid数据库。

　　效果就是，这些数据库可以把单字段的filter结果缓存起来。多个字段的查询可以把之前缓存的结果直接拿过来做 AND 或者 OR 操作。

　　索引存在的必要是因为主存储没有提供直接的快速定位的能力。如果访问的就是数据库的主键，那么需要读取的数据也就非常少了。另外一个变种就是支持遍历的主键，比如hbase的rowkey。如果查询的是一个基于rowkey的范围，那么像hbase这样的数据库就可以支持只读取到这个范围内的数据，而不用读取不再这个范围内的额外数据，从而提高速度。这种加速的方式就是利用了主存储自身的物理分布的特性。另外一个更常见的场景就是 partition。比如 mysql 或者 postgresql 都支持分区表的概念。当我们建立了分区表之后，查找的条件如果可以过滤出分区，那么可以大幅减少需要读取的数据量。比 partition 更细粒度一些的是 clustered index。它其实不是一个索引(二级索引)，它是改变了数据在主存储内的排列方式，让相同clustered key的数据彼此紧挨着放在一起，从而在查询的时候避免扫描到无关的数据。比 partition 更粗一些的是分库分表分文件。比如我们可以一天建立一张表，查询的时候先定位到表，然后再课课家执行 SQL。比如 graphite 给每个 metric 创建一个文件存放采集来的 data point，查询的时候给定metric 就可以定位到一个文件，然后只读取这个文件的数据。