[toc]
[CMU15445] 05 - Database Storage 3
Database Workloads
- On-Line Transaction Processing(OLTP)：每次只对整个数据库的一小部分数据进行读写操作，通常写操作多余读操作，例如你在淘宝购物车中添加商品，下订单等
- On-Line Analytical Processing(OLAP)：每次会对大量的数据进行操作，基本全部为读操作，很少有写操作，并且每次通常只会对一条记录的几个属性操作
- Hybrid Transaction Analytical Processing(HTAP)：同时兼顾了OLAP和OLTP的功能，属于上述两者的结合
Storage Models
存储模型主要分为行存储和列存储
N-Ary Storage Model(NSM)
N-Ary将一条记录的所有字段都连续的存储在一起，所以也叫行存储，适合用在OLTP的场景
优点：
- 由于整个记录是存在一起的，可以快速的对一条记录进行插入，修改和删除
- 对于需要用到整条记录的查询效率很高
缺点：
- 对于一个需要查询大量的数据，但是只需要用到里面几个字段的查询，行存储的效率很低
Decomposition Storage Model（DSM）
在DSM中，将不同记录的相同属性连续的存储，所以也叫列存储，非常适合OLAP的应用场景
对于DSM，一个问题就是当我们需要一整个记录的时候怎么办，通常会有以下方法
- Fixed-length Offsets
对于每一列的存储，所有的字段都是定长的，所以查询特定的字段可以通过偏移量来实现
- Embedded Tuple Ids
在每一个记录中的每一个属性多存储一个Id，单独维护一个map，可以通过id映射到各个字段的位置，这样做需要大量额外的存储空间，所以一般不用这种
总结一下DSM的优点：
- 因为数据是按列存储，对于特定查询某列，只需要读入该部分的数据，减少了不必需要的I/O
- 因为是按列存储，通常一列的数据都来自同样的域(domain)，所以可以更好的支持查询处理和压缩
缺点：
- 因为列存储将一条记录分开存储，所以对于整个记录的查询，插入，更新，删除等操作很慢
Database Compression
通常在一个数据库中，性能的瓶颈总是卡在磁盘上，如果将数据压缩，这样就可以一次从磁盘读取更多的数据，从而提高性能
数据库的压缩需要平衡压缩率和速度，通常将数据压缩的更小在处理时就需要花费更多的时间，所以大多数数据库压缩算法都会有一个较低的压缩率来保证速度
数据库压缩算法有以下要求：
- 数据在压缩后也应该是定长的字段，以便通过offset来索引
- 在需要对数据进行操作时，尽量延迟解压缩的时间，也就是能不解压缩就不解压缩
- 压缩一定是无损的
压缩通常有不同的粒度，可以将整块的数据压缩(block-level)，也可以将每一行(tuple-level)，每一列(column-level)，或者一行中的某一个字段(attribute-level)
下面介绍一些常用的压缩算法：
1.Run-length Encoding
将相同的记录压缩成一个三元组(value,start,length)
在一个已经排序好的数据上压缩效果会更好
- Bit-packing Encoding
如果所有要存储的值可以使用一个更小的数据类型来存储，就换成更小的类型，例如一个int64字段，但是最大的值只有45，就可以压缩成8bit的存储
- Bit-map Encoding
使用一个bit array来存储值，map的每一位表示一种不同的值，通常用于值的种类较少的情况，例如性别
- Delta Encoding
对于时间，温度之类的存储，存储他和上一个数据的差值，可以在这个的基础上对数据压缩，得到更小的数据
- Dictionary Encoding
将一个记录拆成许多word的组合，建立一个字典来记录word，建立一个id到word的映射，在查询时可以将word转换为id，这样就可以直接在压缩的数据上进行查询，对于范围查询，可以将整个字典进行排序
