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

列存储中常用的数据压缩算法列存储,作为一种针对数据查询和数据分析设计的数据存储策略,在“大数据”越来越普及的今天可以说是相当地火热。相较于行存储,列存储的最大优势有二,其一就是查询涉及到数据库的哪几个列就读哪几个列,不读一点与查询不相关的列,大大减少了数据的读取,其二就是数据库数据分为多个独立的列来存储,相同数据类型的数据连续存储在一起,易于数据压缩,而这再次减少了数据的读取。以上正是列存储在处理数据查询和数据分析方面的天

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

其一、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》

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159133.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(1)


相关推荐

  • MySQL字符拼接_mysql查询字符串拼接

    MySQL字符拼接_mysql查询字符串拼接第一种:mysql自带语法CONCAT(string1,string2,…),此处是直接把string1和string2等等的字符串拼接起来(无缝拼接哦)说明:此方法在拼接的时候如果有一个值为NULL,则返回NULL如:1.SELECTCONCAT(“name=”,”lich”,NULL)AStest;2.SELECTCONCAT(“name=”,”lich”)AStest;第…

  • Linux设备树是什么?

    Linux设备树是什么?随着Linux的不断发展,基本上现在所有的驱动程序都是基于设备树的,而设备树到底是什么?有什么作用,Linux内核怎么通过设备树知道外设适配的。文本介绍了设备树、以及分享了一些设备树的基本语法、一些基本属性等,最后简单分析了设备匹配的基本流程

  • 站长关心的广告联盟简单的介绍跟评价[通俗易懂]

    站长关心的广告联盟简单的介绍跟评价[通俗易懂]联盟是每一个开始网络淘金的站长都遇到的问题,很多人吃过亏,比如那个垃圾智易联盟,我知道这里每天只有1000多个人看,但是希望每一个关心网站建设的朋友少走一些弯路,找到自己金矿,呵呵发表时间:2005-11-133:59:37原文作者:心情沙发金山网盟:金山估计会一直烧钱下去的,但是金山的针对性比较强,估计对下载等资源站的效果更好一点。百度搜索联盟:baidu虽然封站,引起站长的仇恨,不过ba

  • pycharm每次运行需选择interpreter_pycharm no interpreter怎么办

    pycharm每次运行需选择interpreter_pycharm no interpreter怎么办新的py文件,点击直接使用pycharm打开,运行报错,interpreteroption为空第一步:选择File,进入Settings。第二步:1.选择Project中的ProjectInterpreter。2.选择下拉中的pathon解释器,如图为3.6的解释权。3.选择Apply,使设置生效。运行代码成功。…

  • linux添加路由网关_linux删除默认网关

    linux添加路由网关_linux删除默认网关1、以前经常使用route命令添加和删除路由添加网关/设置网关:routeadd-net192.100.10.0netmask255.255.255.0deveth0#增加一条到达192.100.10.0的路由。屏蔽一条路由:routeadd-net192.100.10.0netmask255.255.255.0reject#增加一…

  • IDEA汉化之2021版本

    IDEA汉化之2021版本打开最新版本的IDEA后在浏览器直接进入Chinese(Simplified)LanguagePack/中文语言包-IntelliJIDEs|JetBrains,右上角,IDEA中会出现弹窗,直接起飞!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号