数据即索引-大数据索引漫谈

传统意义上的索引，目标是为了加快查询速度，但独立于数据，通常可以加载到内存，典型的比如B-Tree等。

但在大数据里，这点就变得有点trick了，因为即使索引比实际数据小很多，但是因为实际数据实在是大，所以索引依然会很大，很有可能依然无法放入到内存，所以会导致很多传统数据库的索引模式对大数据其实是不work的。因为我对传统数据库的知识有限，所以接下来我重点还是会放在大数据索引相关的思考上。

大数据索引叶子节点通常是chunk(block)/file/cube而不会是最细粒度的Row。一则大数据采用的是列式存储，二则如果到Row级别，我们前面说了，索引会非常非常的大。这说明大数据索引追求的是chunk(block)/file/cube skip,最终目标是尽量减少不必要的文件扫描，但对于定位到的文件，还是需要【暴力】filter 出chunk(block)/file/cube里的记录，最后返回。通过这种模式可以有效减少Task数，因为通常一个chunk(block)/file/cube 对应一个或者多个Task,提升查询速度。

在进一步讨论之前，我们简单说下chunk(block)/file/cube 的概念。 chunk(block)可以组成file,多个file 可以组成一个cube.之所以分成三个层级，是为了方便多个层级的索引构建。比如执行cube的索引就可能非常小，其次是file, file里面又可以自己包含block的索引。比如Carbondata就是到block级别的。

前面我们提到，本质上大数据的索引是在做 file skip(你定位到一个cube其实就是为了找到一组file,或者你找到一个block,你也需要找到block所在的file)，精准定位file集合可以有效的减少task数目，提升查询速度。而通常对于一张表，文件数总数是不会很大的(毕竟HDFS的文件数量也是有上限的），比如几千到几十万。这个时候就可以很好的使用B-Tree等索引了，当然，实际上数据这么小的情况，我们还可以直接使用一个线性结构保存，需要的时候过滤下即可，不一定需要使用树结构（越简单越好）。但是，大数据其实对单表查询并不多，反而是多表关联子查询特别多，意味着我们最终单表我们还是要过滤出非常大量的数据，而结果集越大，那么可能命中的file数越大，对于条件

from table1 where x>100 && y< 100000

假设table1有一万个文件，如果记录是随机分配到一万个文件，那么大概率where x>100&& y<100000 的记录就会散落在所有的文件里，这个时候file skip的意义就没有了，因为这意味着我们需要访问访问所有的文件。所以，为了能够让file skip变得有意义，我们需要确保数据按一定分布规则分布到这一万个文件里。对于where x>100&& y<100000，我们可以用z-ordering index将x,y这个二维的过滤条件转化成一个一维的地址，这样我们就地址按区间分布到这一万个文件里，这样就可以让file skip起作用。

前面我们得到结论，无论如何，在大数据里做索引，本质上都是为了实现file skip,而file skip必然要改变数据的在文件集合里的分布情况。从某种意义上说，带有一定分布规律的数据自身就是索引，我们传统所说的索引只是保存了这种分布规律。

这个事实其实会带来一个比较有意思的结果，就是大数据里的索引和数据可以保持一样大。而在传统数据库中，索引可能远小于数据，也可能远大于数据。因为通常一种数据分布只能满足一定类型（或者维度组合的）查询，所以为了满足多种查询需求，我们可能需要多种数据分布，那么就需要有N份数据的存储。所以我觉得数据湖应该要拥抱这个事实。

通常而言，这是一种无损的索引模式，因为即使我们不能利用数据分布加快数据的查询速度，但是我们依然可以回退到【暴力】扫描从而得到正确结果。比如用户的查询不符合z-ordering index的要求，我们依然可以跳过z-ordering index得到正确的结果，付出的代价不过是降低了响应速度。

而我们以前数仓分层模型里提到的视图概念，尤其是最近开始火热的物化视图，则是一种有损索引模式。在物化视图里，里面本质上存储的也是数据，但是这个数据不是简单的改变了数据在文件集合里的分布，而是直接做了提纯，所以他只能满足特定查询。尽管如此，物化视图满足前面我们提及的数据即索引的规则。

大家对布隆过滤器有一定的了解，他是一个并不精确的算法，通过一些组合维度判定一条记录是不是已经存在。通常我们可以为每个file准备一个布隆过滤器，也可以为一个cube准备一个布隆过滤器，这取决于你的内存需求，然后因为布隆过滤器判定一个row不在，那他一定不在，而如果他判定在，则可能在，所以我们可能会将一个不包含某个row的文件判定为包含，但不会将一个实际包含了某个Row的文件判定为不包含，也就是说会多出一些文件，但是因为我们只是为了减少不必要的文件，而不是一定要精确的进行判定，所以布隆过滤器显得非常有用。然而，他从某种角度完全可以被z-ordering index所取代，因为z-ordering index可以实现多维度组合的file skip。但是为什么我们可能还是偏向于使用布隆过滤器呢？z-ordering index需要改变数据的分布，这意味着我们可能为此需要多付出一倍存储的代价，而布隆过滤器则会小很多，然后可以被载入内存。但是如果话说回来，某种角度而言，数据分布是必须要满足的，在某些场景，如果不满足数据分布，布隆过滤器可能会发挥所有的文件，这甚至会有损性能。

总结下，以物化视图为代表的有损索引，和以z-ordering index为代表的的无损索引，本质上都是以数据分布作为索引。大数据索引解决的核心问题是file skip而非rwo skip, 而file skip必然会带来数据在文件集中的分布要求，为了满足多样化的查询，从而使得数据发生膨胀，而膨胀率则是索引（数据分布）的数量N*数据大小。