列式存储的起源：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 挺有意思的。