内存数据库和面向磁盘的数据库的存储模型与数据分布差别不大（？）

字节对齐

注意元组的字节对齐以便Cache的读写而不需要进行什么额外操作。

未经处理的字节对齐.png

在这里要读cdate的时候可能会需要进行额外的读，为了读完成的cdate需要读第一个第二个两个word；或者随机读，（可能从一个word中间往后读64bit？）;或者出错，异常

要解决这个问题，可以

1. Padding，不满一个word的占一个word，剩下的空间空着。
2. 重新排序，对于空的地方考虑和后面的属性共用，如上面的id和zipcode一起占一个word

存储模型

行存储和列存储

行存储 N-ary storage model(NSM)

OLTP 方便写
用的是Tuple-at-a-time 迭代器模型

物理实现上有两种选择：基于堆的表，元组乱序存放在堆中；基于索引的表，元组存在主键索引中，是有序的（主键索引和聚集索引有什么区别①）。

优点：方便插入更新和删除；对于需要整个元组的查询很方便；能用面向索引的物理存储结构；
缺点：对于只查找部分属性的查询来说额外占了很多空间

列存储Decomposition storage model(DSM)

用vector-at-a-time迭代器模型

对于元组属的区分，两种方法：定长偏移，所有的属性都是同样的长度；嵌入元组id，每个属性的存储实际是两列，元组id+对应的属性

优点：查询时只读需要的数据节省空间；因为同一个属性存的东西也差不多，便于压缩；
缺点：由于一个元组被分割了，查询整个元组、插入、更新、删除都慢

混合存储模型

数据第一次进入数据库是热数据，一个最新插入的元组很有可能马上需要更新；元组越老，更新频率越低，一些情况下，一个元组只会和其他元组一起被访问。
基于以上事实，考虑把刚插入或更新的数据用行存储，老的数据用列存储，也就是混合存储模型。
两种模型：

1. Separate Execution Engines：对于NSM和DSM用不同的特殊优化的执行器；最终需要把两个结果合并；如果一个事务在两个都进行操作了，需要考虑同步问题（如用2PL）。
   Fractured Mirrors：存一个DSM的自动更新的镜像，所有的更新都进到NSM中，之后再copy到DSM中

   
   Fractured Mirrors.png
   

   Delta Store：更新存在NSM表中，后台线程把更新再迁移到DSM中。

   
   Delta Store.png

此外还需要考虑那些数据要存到DSM中，谁判定，怎么判定，什么时候存。

目录

几乎所有的DBMS都存自己的目录，引导目录表的特殊代码。

Schema Changes

• 加一列：NSM存到新的地方；DSM加一个新的空间column segment
• 去掉一列：NSM可以存到新的地方也可以标注这一列无效；DSM直接把这一列删掉释放内存。

索引的创建：先扫描整个表，产生索引，记录在构建索引过程中的其他事物对这个表做出的修改；扫描结束后，锁住表，然后解决在扫描开始后发生的修改（写入到索引上）。
索引的删除：从目录中逻辑删除。而那些还在用这个索引的事务继续用，而且仍需要更新索引（仍要保证此时事务间的一致性）。

---

①主键索引和聚集索引：聚集索引指的是物理的存储顺序，但主键索引是在主键上构建的索引（和其他在非唯一的属性上构建的索引没有区别）。在相当多的数据库中，如Mysql的innodb中，主键索引和聚集索引确实是等价的。