列存储中常用的数据压缩算法

大家好，又见面了，我是你们的朋友全栈君。列存储，作为一种针对数据查询和数据分析设计的数据存储策略，在“大数据”越来越普及的今天可以说是相当地火热。相较于行存储，列存储的最大优势有二，其一就是查询涉及到数据库的哪几个列就读哪几个列，不读一点与查询不相关的列，大大减少了数据的读取，其二就是数据库数据分为多个独立的列来存储，相同数据类型的数据连续存储在一起，易于数据压缩，而这再次减少了数据的读取。以上正是列存储在处理数据查询和数据分析方面的天然优势，其中也有很多值得探讨的东西。关于前者，本博主涉其未深，不便胡说，倒是近日通过阅读些许文章晓得了几种列存中的数据压缩算法，可以写出来与众看客们分享一二三点。

其一、Run-Length Encoding，其核心思想是将一个有序列中相同的列属性值转化为三元组（列属性值，在列中第一次出现的位置，出现次数），适用于列有序或者列可以转化为有序且列中distinct值较少的情况。图一给出了一个简单的示意图，其中一个排好序的列仅包含两个distinct值，通过Run-Length Encoding，整个列使用两个简单的三元组就可以表示了。使用这种算法，一个列可以转化为多个三元组，通过在这些三元组上构建B树索引就可以轻松地实现对该列的管理。

其二、Bit-Vector Encoding，其核心思想是将一个列中所有相同列属性的值转化为二元组（列属性值，该列属性值出现在列中位置的Bitmap），适用于列无序且无法转化为有序但列中distinct值较少的情况。图二给出了一个简单的示意图，其中一个无序的列仅包含两个distinct值，8000这个值分别出现在列中的0、3、4、6四个位置,3000这个值分别出现在列中的1、2、5三个位置，使用位图便可以表示出来，通过Bit-Vector Encoding，整个列使用两个简单的二元组就可以表示了。使用这种算法，一个列可以转化为多个二元组，通过在这些二元组上构建B树索引就可以轻松地实现对该列的管理。此外，如果列中distinct值较少，那么二元组中的位图就会很稀疏，所以位图还可以使用上面的Run-Length Encoding进行二次压缩。

三、Dictionary Encoding，其核心思想就是利用简短的编码代替列中某些重复出现的字符串，通过维护一个编码与被替代字符的映射就可以快速确定编码指向的是哪个字符串，这个映射也就是所谓的Dictionary，适用于列中存在很多相同字符串的情况。这里不妨以Google在VLDB2012上发表的论文为例来说明Dictionary Encoding的妙处。图三给出了该论文中一个示例（原论文中示例有误，即图中红圈标注处，可忽略），其中一个名为search_string的列被分成了三个块（chunk），在每个块中都存在重复的查询字符串。

为了压缩每个数据块的大小，首先创建一个全局字典表global-dictionary，该表中存储search_string列中所有的distinct字符串，且每个字符串均对应一个全局id，譬如amazon的全局id就是它前面的1。其次，每个块中也创建一个块字典表chunk-dict，该表中存储了块中所有的distinct字符串在global-dictionary中的全局id，且每个全局id均对应了一个块id，通过这种二级字典表的方式，一个字符串就可以通过全局字典表映射到一个全局id，再通过块字典表映射到一个块id。所以，此时块中也不再存储真正的查询字符串，而是存储查询字符串对应的块id，即图中所示的elements。譬如要查询chunk 0中第4个element真正代表的值时，需要使用该element的值4到块字典表中查询得到它对应的全局id为12，然后在使用12到全局字典表中查询得到12对应的字符串是“yellow pages”。使用这种算法，一个存储了查询字符串的列就转化成了存储32位整型值的列，数据空间大大缩小。

以上便是列存储中常见的几种数据压缩算法，当然这些算法都是列存储中的专用方法，其他像Snappy、zlib、LZO等通用压缩算法在列存储中也有十分广泛的应用。通常针对同一个列往往可以使用多种压缩算法进行多次压缩，效果更好！

参考文献：《C-Store: A Column-oriented DBMS》和《Processing a Trillion Cells per Mouse Click》