在OLAP存储引擎中，索引犹如书的目录能够快速定位所查的数据，直接在数据源端把无关的数据过滤掉, 只把满足条件的有效数据参与计算。现在即便有各种硬件加速（GPU, FPGA等）以及Vectorized Processing (如monetdb, Vectorwise，clickhouse等)，这些新技术能够极大提高数据处理的吞吐，加速查询；但“古老”的索引技术也一直是研究的重点，尤其在OLAP领域a.索引造成的数据膨胀与OLAP海量数据高压缩需要的矛盾；b.海量数据索引构建与有限资源的矛盾，需我们去找一个更好的解决方案。
介绍前先介说下索引的分类，便于读者不迷失方向。索引的分类其实是个比较难的问题，不同视角有不同的分法: 比如从维度方面考虑，可以分1. 一维索引（Bitset类，B-Tree类, Trie类，Skiplist类等），2. 高维空间索引(KD-Tree, R-Tree等)；而数据库的索引一般有主键索引，二级索引，聚集索引，唯一索引等。本文主要从影响OLAP存储设计维度来介绍一些的重要索引机制:
a. 隐性索引
b. 聚集索引
c. 二级索引
d. 粗糙集（Knowledge Node）
e. 倒排索引
f. 自适应索引
1. 隐性索引
表的“分区”是具有索引属性的，“分区”决定了数据的分布，查询时可以通过查询条件进行“分区裁决”来优化查询。分区常见的有一级分区，二级分区或。业务上通常通过一级分区把数据分布在不同的节点，通过二级分区对数据进行生命周期管理。
2. 聚集索引
聚集索引是指数据库表行中数据的物理顺序与键值的逻辑（索引）顺序相同。像传统的OLTP数据库，主键索引一般是聚集索引(postgresql不是)。即使没有主键索引，也会默认以rowId作为聚集索引，聚集索引一般只有一个。在OLAP领域，主键索引不一定实现成聚集索引，而且聚集索引也可以多个。聚集索引不仅有索引的功能，还能够决定数据的物理布局，对某些查询能够很好优化io性能，比如select c1, c2, c3 from t1 where id < 1000 and id > 100; id列是否创建聚集索引，会导致最终底层访问的IO情况截然不同。
OLAP的列式存储可以拥有多个聚集索引，比如C-Store(http://db.csail.mit.edu/projects/cstore/)的projections概念，C-Store 通过数据冗余，可以按不同维度创建多个projections, 其中一个projections一定要包含所有的列，剩余的可以只需要冗余部分列。 如下图: table 有saleId, date, region, prodid四列，
由于列存数据的高压缩特性，以及只需要包含指定的列，多个聚集索引只要在业务层合理规划下，整体开销相比带来的效益是可以接受的；对于行存多个聚集索引的整体开销会大很多。
3. 二级索引
二级索引是一种非聚集索引，非聚集索引制定了表中记录的逻辑顺序，但是记录的物理顺序和索引不一定一致。一般聚集索引的key由原表二级索引列+ PrimaryKey构成，使用时通过二级索引列查到满足条件的PrimaryKey;再通过PrimaryKey反查原表。
二级索引一般不会创建太多的，考虑到动态构建二级索引IO和CPU开销, 以及数据膨胀带来的存储开销。对于一个实时系统，由于数据的动态变化，相比静态数据要想获取很高的压缩更具挑战；同时如果是实时随机更新数据，索引的维护会产生很严重的IO放大。当然如果是对于静态数据，同时采取批量更新的模式那就能比较好的控制数据膨胀和IO放大，一般倒排索引就采用模式。
二级索引的选择和使用是一个很有挑战的话题。简单说如果系统每次可以使用一个二级索引，那么就根据统计信息使用筛选率最高的那个；如果系统可以使用多个二级索引，最简单方式是是每个二级索引都用上，但事实上最佳方式可能只需要使用一些，剩余的列直接过滤。
4. 粗糙集（Knowledge Node）
这个定义估计说不好，直接上例子。粗糙集使用最具代表的是Infobright，Infobight把数据分成两层，如下图:
底层是压缩的数据块（Data Packs）,它存储用户实际的数据，上一层是知识网格(Knowledge Grid),它里面存的是Data Packs的一些统计信息，比如对应的Data Packs里面数据的MIN, MAX, SUM, AVG,COUNT, and No. of NULLs以及数据分布的直方图. 查询引擎利用Knowledge Grid把查询无关的Data Packs高效的筛选出，避免全表scan.
这种基于粗糙集的策略，在列属性物理布局有一定规律的情况效果会很好，比如表按ID递增方式存储，那么对于select * from t1 where id < 1000 and id > 100这种查询效率会非常高，但如果列属性是完全随机物理布局的，那么Knowledge Grid就起不了很大的作用。
5. 倒排索引
倒排索引最核心的索引组织如上图:词典, 倒排链, 以及词典的索引。对于查询如select * from table where name = “Ada”or name = “Sara”, 我们可以利用倒排索引把term = “Ada”和 term = “Sara”的倒排链获取到，然后把目标倒排列进行or操作，就得到了我们的目标行号，然后再按需反查明细。倒排索引是一门非常复查的技术，深入研究可以参考lucene。倒排索引对存储一个重要的影响是，倒排索引的倒排链一般存的是行号（相比主键更好压缩，存储空间少），存储的数据一旦行号变化了，那么倒排索引需要进行更新甚至重构。像innodb, myrocks这些基于B-tree或LSM-tree的存储底层都是按主键排序的，在数据更新时数据的行号可能会发生改变；postgresql的存储由于引入tuple identifier (TID) ，由block num和内部offset构成，可以看成行号，但不能保证连续递增，平时在增删改时能够维持不变，只有在空间整理时才改变。以倒排索引为核心索引的存储一般采用“append + 标记删除”模式, 来保证行号不变，减少索引的重构。
只考虑单列的倒排索引和二级索引有点像，倒排索引构建也会面临:
a) 数据膨胀
b) IO消耗
c) CPU消耗问题。
6. 自适应索引（Adaptive Indexing）
Adaptive Indexing属于Database Cracking范畴，Adaptive Indexing的目标和动机：
- 让用户不感知非业务相关的索引（像主键索引，唯一索引这种和业务相关，为加速查询的索引为非业务相关），对用户使用友好
- 在有限的资源下，能够平衡好索引构建的资源开销和查询性能, Daniel Abadi在The Design and Implementation of Modern Column-Oriented Database Systems提到了3个特征
a) 自适应性: 在系统空闲或者我们需要时才做
b) 部分性: 只构建所涉及数据的索引
c) 连续性: 系统能够不断向最优方案迭代
一个简单例子: 以Monetdb为例，Monetdb的数据按列存储，称为BAT(Binary Association Table)对于下面查询:
Q1. Select * from R where R.A > 10 and R.A < 14
Q2. Select * from R where R.A > 7 and R.A <= 16
Monetdb能够在查询的过程同时进行了索引的增量构建
索引技术是一门很深的话题，本文只是简单介绍了OLAP引擎常见的一些索引，通常OLAP引擎也只会以某一种索引作为其主要的策略。
文献参考:
- Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries
- The Design and Implementation of Modern Column-Oriented Database Systems
- Monet; a next-Generation DBMS Kernel For Query-Intensive Applications
- Database Cracking: Towards Auto-tuning Database Kernels
- http://www.interdb.jp/pg/pgsql01.html
