专栏首页Apache IoTDB列式存储的起源:DSM

列式存储的起源:DSM

列式存储模型并不是最近十几年才有的,早在1985年就有人提出了类似的思想,即 Decomposition Storage Model(DSM)。 那么他把谁 decompose 了呢?那就是行式存储模型 N-ary Storage Model(NSM)。

参考1985年的《A decomposition storage model》一个 PPT。

NSM vs DSM

NSM:N元存储模型,也就是行式存储模型。数据的物理结构和他们的逻辑结构是一样的。磁盘是由一个一个block组成的,因此连续的数据也分在了连续的block里。逻辑和物理的对应关系如下图:

DSM:分解的存储模型,其实是关系表的一种设计方式,即每一行记录都分解成二元关系表,每个二元表对应一个属性加一个ID主键,这样两张表还可以 Join 起来。逻辑和物理的对应关系如下图:

DSM的结构优势

避免空值:分解之后,就不用属性之间对齐了,对于稀疏数据来说,能有效避免空值的存储,节省空间。

减少数据冗余:能让逻辑清晰,即范式化。在NSM中,如果不对照两个表的SS#字段,则不能区分 Nicole 是重名的还是一个人,存在一张表里可以清楚的看到 Nicole 就是一个人。

Differential File

首先介绍一个概念,叫 Differential File(差异文件,参考《Differential Files: Their Application to the Maintenance of Large Databases》)。类似图书后边的勘误表,和 LSM 的概念差不多,主要为了减轻数据更新负载。当更新一个记录(一行数据)时,不直接修改原始记录,而是将整个新的记录写在一个 Differential File中,这个文件的格式和原表一样,每修改一个记录这里就多一个记录,当这个文件大小超过一定阈值,就合并两个文件。

简单介绍一下 Differential File的优势:

(1) 在没有Differential File 时,要想防止磁盘损坏导致数据丢失,需要定期全量备份数据库,而有了 Differential File,只需要一次全量,后边只增量备份 Differential File 就可以了。

(2)每次定期备份的时候,需要数据库状态一致,即备份时拒绝修改。通过增量备份很小的 Differential File,则可以避免这个限制。解法是在备份时维护一个 differential-differential file,即在当前备份状态(原文件-差异文件)上的差异文件。但是这样搞有个前提:Differential file 比较小,大了就傻逼了。

(3)方便测试,一份不可修改的数据,两份差异文件,可以同时运行两个系统,每个系统维护一份数据和自己的差异文件。一个生产系统,一个测试系统,可以随时debug。

(4)由于原始文件不可修改,支持简单的并发访问。

其实 Differential File 到底是存一整行数据还是仅仅存储被修改的属性,仅仅是个实现问题,这里采用了完整数据。

DSM的更新查询优势

差异文件主要是记录数据库的更新的,在存储完整记录的配置下,NSM和DSM有啥区别呢?显然DSM需要记录的信息少啊!如下图:

由于DSM模型中每个表都只有两列,因此在其上构建索引和查询引擎也很简单。

DSM的缺点

可以看到,NSM 中 ID 只用存一次,但是 DSM 中 ID 需要存很多次。会占用更多磁盘空间。

在更新时,每修改或增加一条 NSM 中的记录,仅需要更新一个完整记录,但是 DSM 中需要为每个二元属性表修改一次记录。如果在表上构建索引,索引的操作也更多。

这些缺点基本是和存储特点绑定的。

总结

DSM 可以说是列式存储的起源之一了。关于这个 DSM 没啥特别有意思的,主要是一种表的设计方式,但是其引申的 Differential File 挺有意思的。

本文分享自微信公众号 - IoTDB漫游指南(Apache-IoTDB),作者:铁头乔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-06-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 大数据与大数据计算

    今天听了一场报告会,是清华计算机系60周年系列讲座之一,主讲人是哈工大软院院长李建中教授,主题《计算和数据资源受限的大数据计算的复杂性理论与高效算法研究》,李老...

    Apache IoTDB
  • 和谐号为啥快?因为铁轨是列式存储!

    今天不讲和谐号,今天讲列式存储!列式存储是大数据时代的一个特色。每次一听用到了列式存储,就觉得,嗯,肯定nb了。今天我们就来把列式存储的衣服扒了!咳咳,,,揭开...

    Apache IoTDB
  • Fractured Mirrors:破碎的镜像

    今天介绍《A Case for Fractured Mirrors》,来自 VLDB 2002,作者来自威斯康星大学麦迪逊分校,和之前的 PAX(Partiti...

    Apache IoTDB
  • 致自学编程的朋友,我想给你们几个建议

    很多人都想转行互联网,不管是出于兴趣、行业前景还是薪资的考虑,想要转行互联网的人们必须要面对一个问题,那就是如何自学编程,更确切的说,是如何0基础学编程。

    乔戈里
  • 自学编程的朋友,我想给你们这 5 个建议

      很多人都想转行互联网,不管是出于兴趣、行业前景还是薪资的考虑,想要转行互联网的人们必须要面对一个问题,那就是如何自学编程,更确切的说,是如何0基础学编程。

    黄小斜
  • 给Python初学者的6个实用建议

    编程作为一项技能,需要长期的训练以达到熟练的地步。每天写一点代码,保持对代码、语法和逻辑的敏感度,有利于初学者巩固新接触的知识和概念。

    州的先生
  • 【LeetCode第 177 场周赛】5172. 形成三的最大倍数

    给你一个整数数组 digits,你可以通过按任意顺序连接其中某些数字来形成 3 的倍数,请你返回所能得到的最大的 3 的倍数。

    韩旭051
  • 编程小白 | 每日一练(190)

    这道理放在编程上也一并受用。在编程方面有着天赋异禀的人毕竟是少数,我们大多数人想要从编程小白进阶到高手,需要经历的是日积月累的学习,那么如何学习呢?当然是每天都...

    C语言入门到精通
  • FunDA:一个开源的函数式数据处理工具库,也是Slick的补充

      如果你是一个Slick用户,或者你是一个数据库编程人员正在尝试进入函数式编程模式,那么FunDA可能会帮到你。 目前市面上FRM(Functional Re...

    用户1150956
  • 23岁学编程太迟?都这把年纪了,别瞎折腾了

    最近几年大家都感受到互联网给我们生活带来的变化,移动支付、共享单车、外卖等等等,完全改变了我们的生活方式。其他行业也逐渐离不开互联网,互联网俨然已经成了基础设施...

    老九君

扫码关注云+社区

领取腾讯云代金券