大数据即时计算产品的一般原理----索引

一、基本概念

      索引相信大家多多少少都接触过，索引的目的说白了就是加快数据的检索、排序和计算等，尤其是对于海量数据的快速检索，索引起到了至关重要的作用。大家都知道，我们基于传统数据库开发经常会遇到一个问题，就是这个SQL查询变慢，是不是索引没加？数据库的索引好比一本书前面的目录，如果明确知道按哪个字段来进行索引查找，查询效率还是挺高的，数据库的索引实际上是一个单独的、物理的数据库结构, 它是某个表中一列或者若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单，但是大家一定要注意，并不是所有的数据库索引都能提升查询性能，毕竟传统数据库主要还是面向事务的，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，而创建索引和维护索引却要耗费时间，这种时间随着数据量的增加而增加，并且每一个索引还需要占用存储空间，所以事务型关系数据库经常会考虑平衡修改性能和查询性能，灵活度受限，甚至需要专门的DBA来进行REVIEW。而对于数据仓库的应用来说主要还是以读为主，而对于查询条件的灵活度以及查询响应结果的速度要求还是蛮高的，特别是对于OLAP应用，查询条件维度灵活组合，另外还经常有类似于LIKE这样的模糊查询，大家可以想象一下，这在关系数据库在面临海量数据检索时是很难进行支撑，光是索引也还是很难建的。所以现在大家对于大数据场景下的检索一定会想到LUCENE，关于LUCENE的技术知识，这里就不展开多讲，ATA就有很多文章介绍，我这里主要摘出LUCENE索引的两个重要的概念：

1、倒排索引：
又称反向索引，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。倒排索引由词典和倒排表组成，字典是由索引词组成的索引表，而倒排表则由每个索引词出现过的文档集合，以及命中位置等信息组成的记录表。如图所示：

在处理复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取。这样不必对每个记录随机存取，把对记录的查询转换为地址集合的运算，从而提高查找速度!

2、正排索引：
也称前向索引，主要由正排表组成，正排表中每条记录表示一个文档的属性集合,以文档ID 为主键,表中每个记录的索引字段记录了文档的每个属性字段的值。正排表/属性(Attribute) 主要用来进行过滤,统计,rank/排序.在一次查询中,倒排表集合运算后的文档集合中的每个文档后续都需要访问其相应的正排表/属性(Attribute)数据,来进行过滤,统计,算分,排序等,所以正排表/属性(Attribute)访问速度需要非常快,通常需要常驻内存。

二、索引对于大数据即时分析型数据库的好处

• 倒排索引对于大数据检索的支持非常灵活和高效，基于倒排索引的过滤不需要进行大量的IO扫描（用于sql的 where过滤）。
• 可以利用倒排表的词频统计信息，快速用于求COUNT查询，百亿数据10台机器百毫秒级别响应。
• 倒排索引容易压缩，特别对于重复值比较多的情况下，压缩程度非常高，极大减少IO，另外倒排表本身采用了delta存储，比如说第一个值为 xiaogu12353,第二个值为xiaogu12354,那么仅仅存储他们的差异即可。
• 正排索引技术可以很方便实现对于GROUPBY的字段进行编号，比如按国家名称来统计PV，可以将国家全称的长文本信息统一编号为int型数值代号，将极大节省IO。

三、索引技术在大数据即时计算中的运用

上段基本描述了索引至于大数据即时计算带来了诸多的好处，那么实际索引技术又是在大数据即时计算哪些技术环节进行了使用？我总结了下HIGO和GARUDA（有些YY），大体都是这样一个基本流程：

 
HIGO本身是基于lucene和Solr开发，所以在数据检索和统计上完全依赖于Lucene的倒排索引和正排索引，用户输入一个term(词)，通过倒排索引快速获取docIdList,然后通过正排索引获取docId->Field文件存储的位置，具体是fdt和fdx文件，出于性能考虑，很多Field的值都以FieldValueCache的形式载入到内存里进行统计计算，缓存的构造也充分利用索引文件可压缩可转编码转换处理的特性，极大节省了存储容量和IO。GARUDA目前也自己实现了一套倒排索引和正排索引，大概计算流程如下图所示：

从上图可以看到通过倒排索引可以找到term->rowIds,再从正排找到rowId->columns(列存储位置)，再进行过滤、统计、聚合最终返回结果，大致的流程也差不多。

   最后总结一下，索引技术之于大数据即时计算，除了大幅加快数据的检索速度还显著减少查询中分组、统计，大幅提升系统的性能和响应时间。据了解，腾讯和百度等互联网公司也在积极研发基于大数据索引技术的分析型数据库，所以索引技术也是大数据时代的利器。