高级数据库十一：存储模型和数据布局

灰太狼 2022-06-01 23:14 308阅读 0赞

# 存储模型和数据布局（Storage Models & Data Layout） #

对于内存数据库而言，它的结构大致如下

可以将之理解为一个大的数组，通过索引（或者直接扫描全部内存）得到所需要的值和存储地址，则通过页和页偏移等信息找到需要的数据。

如果页面是不定长的数据块，可能需要做一个二次指针才可以。

![15143082471015.jpg][]

## 类型表示 ##

*  INTEGER/BIGINT/SMALLINT/TINYINT  
    
    
     *  C/C++ 的表示方法
 *  FLOAT/REAL vs. NUMERIC/DECIMAL  
    
    
     *  IEEE-754 Standard / Fixed-point Decimals
 *  VARCHAR/VARBINARY/TEXT/BLOB  
    
    
     *  Pointer to other location if type is ≥64-bits
     *  Header with length and address to next location (if segmented), followed by data bytes.
 *  TIME/DATE/TIMESTAMP  
    
    
     *  32/64-bit integer of (micro)seconds since Unix epoch

感觉这儿怎么翻译都不太准确，就直接看就好了。

### 可变精度数字 ###

如，FLOAT, REAL/DOUBLE

使用原生C/C++类型的不精确的可变精度的数字类型。这样的优点就是，它的速度比较快；缺点就是会损失精度。

举个例子

#include <stdio.h>
    int main(int argc, char* argv[]) {
     float x = 0.1;
     float y = 0.2;
     printf("x+y = %.20f\n", x+y);
     printf("0.3 = %.20f\n", 0.3);
    }

这样的结果是

x+y = 0.30000001192092895508 0.3 = 0.29999999999999998890

因为C++存的不是精确的数字，所以当精度过大的时候，会有一定误差。这个就像你判断两个浮点数是否相同，不能用`a=b`而是应该用`abs(a-b) <= 1e-6`这样的方法。

### 固定精度数字 ###

具有任意精度和比例的数字数据类型。当浮点错误不可接受时使用。

*  例如：NUMERIC，DECIMAL

通常存储在精确的，可变长度的二进制表示中，并附加的元数据。

*  与VARCHAR类似，但不作为字符串存储

以NUMERIC的结构为例子

![15143096510391.jpg][]

但是这样处理起来，就不能直接用计算机底层指令，而是需要写一些更复杂的逻辑去处理这些东西，比如，手写高精度。所以速度会慢很多。

## DATA LAYOUT ##

CREATE TABLE AndySux ( id INT PRIMARY KEY, value BIGINT );

![15143103694077.jpg][]

在这儿，我们知道header的大小，通常是4 Bytes。

用`reinterpret_cast<int32_t*>(address)`读取id，无论从该地址开始的是什么数据类型，现在就按照int32\_t的指针进行解码。

### NULL数据类型 ###

1.  Special Values：用特殊值去表示某些数据类型的NULL，比如，INT32\_MIN。
2.  Null Column Bitmap Header：在头部存储一个Bitmap去表示哪些属性是NULL。
3.  Per Attribute Null Flag：在每一个属性中存储一个flag表示是否为NULL。需要用更多的空间，而不是一个单独的bit，因为这会导致字对齐混乱。

#### 字对齐 ####

例如，MemSQL的定义是这样：

![15143107192194.jpg][]

关于字对齐，虽然是这样设计的，但是CPU并不是这样读取的。事实是，我们只需要担心缓存行的字对齐（例如64字节）。

元组中的所有属性必须是字对齐的，以使CPU能够访问它，而不会出现任何意外的行为或额外的工作。

![15143108890619.jpg][]

如果CPU从箭头的位置读cdate，而且cdate不是64 bits的，那么有三种可能性。

*  执行两次读取，加载数据字的相应部分并重新组合。
 *  读取一些意想不到的字节组合成一个64位字。
 *  抛出异常

所以在我们将一个元组丢进内存的是，为了避免CPU做一些奇怪的事情，我们会浪费一些空间，来填充这些空间。

![15143111824852.jpg][]

## 存储模型 ##

### N-ARY STORAGE MODEL (NSM) ###

水平的行存储，将每条记录的所有字段的数据聚合存储，即，DBMS将单个元组的所有属性存储在一段连续的内存中。

优点就是数据加载非常快，因为一行数据都是放在一起的。所以插入、删除、修改的速度非常快，是OLTP工作负载的理想选择。适合查询整个元组信息的查询操作。

缺点是其中事务往往只能在单个实体上运行。因为无法避免读取不必要的列，而无法提供海量数据的高性能查询。此外，由于混合存储了不同类型的数据列，实现高压缩也很不容易。

![Center][]

### 物理存储模式 ###

堆结构的表

*  将元组存在名为堆的block中
 *  堆不需要是有序的

索引导向的表

*  元组存在索引上。
 *  和聚集索引不一样。

### Decomposition Storage Model (DSM) ###

垂直的列存储，将相同的字段聚集存储。

有两种方式

每个元素都是定长的，这样就可以通过偏移直接取得某个值。

![15143344438019.jpg][]

每个元素都附带着id。这种方式仅仅是在论文上实现了，实际工业生产中并没有数据库采用这种方式。

![15143344921317.jpg][]

优点是：

1.  因为列的数据已经排序好了，所以不需要索引。
2.  减少浪费的工作量，因为DBMS只读取所需的数据。比较适合OLAP。
3.  更好地压缩，比如，用RLE。

缺点是：

1.  因为元组被切割了，所以插入、删除、修改的时间比较慢

### Hybrid Storage Model ###

混合模式。在将混合模式之前，我们先看看一个现象。

#### 热数据与冷数据 ####

一个数据刚进入数据库的时候，它被称为热的，因为它有极高的可能性在近期内被修改。

而当这个数据的年龄越来越大，它逐渐变冷，那么它被读取的次数将远大于修改的次数。

![15143360745284.jpg][]

大家还记得上节课提到的数据库模型吧。实际上，OLAP数据库通过分析也会将一定的数据写回OLTP数据库。而这几个读取写回的过程需要消耗很多的时间。

#### 混合型存储 ####

对于单一逻辑数据库实例，应对冷热数据使用不同的存储模型。

将新数据存储在NSM中以实现快速OLTP  
将数据迁移到DSM以获得更高效的OLAP

对外看上去是一个数据库系统，但是实际上是由多种模式组成的。

#### 独立的执行引擎 ####

使用针对NSM或DSM数据库进行了优化的独立执行引擎。即，每个DBMS只能在DSM或NSM数据上运行。

*  需要将来自两个引擎的查询结果组合为应用程序的单个逻辑数据库。
 *  如果txn跨越执行引擎，则必须使用同步方法（例如2PC）。

两种方法来做到这一点：

1.  Fractured Mirrors (Oracle, IBM)
2.  Delta Store (SAP HANA)

##### FRACTURED MIRRORS #####

有点数据库类似读写分离。创造两个一样的数据库。

以NSM为主，所有的信息都都先进入到NSM部分，再自动更新到DSM的镜像数据库。

![15143366288510.jpg][]

因为更新有延迟的缘故，如果OLAP在DSM中查询不到，则需要去NSM查询。最终的数据会存在两个数据库中。

##### DELTA STORE #####

和上面的模式类似，但是更新的方式是从DELTA STORE往DSM进行更新。

![15143366909082.jpg][]

数据不会同时存在Delta Store和DSM中，仅存在于其中的一个。这是和上一种方法的差异。

##### 数据分类 #####

1.  人工决定哪个表存在DSM中
2.  DBMS通过log决定哪个表存在DSM中
3.  DBMS通过运行时间决定哪个表存在DSM中

#### 单一，灵活的架构 ####

使用能够在NSM和DSM数据库上高效运行的单个执行引擎。这是我们比较常用的方式。

##### PELOTON适应性存储 #####

*  不需要存储数据库的两个副本。
 *  不需要同步多个数据库段。

![15143373607895.jpg][]

对于这两个查询，系统会自动判断冷热数据，并进行分开存储。

##### TILE ARCHITECTURE #####

引入一个间接层，抽象查询运算符元组的真正布局。

![15143375710754.jpg][]

## 参考资料 ##

[课件][Link 1]

[15143082471015.jpg]: https://lh3.googleusercontent.com/-wvEjBRv2zw4/WkL2gyvriOI/AAAAAAAAAYU/vkR3OPD1dBwOol2nTArdZrdY-1GLGimsACHMYCw/I/15143082471015.jpg
[15143096510391.jpg]: https://lh3.googleusercontent.com/-PlxNf1aGOkY/WkL2hQKd5uI/AAAAAAAAAYY/WgSVUQXdeW4i7w8fHrlFZZ5MQp8e85yXwCHMYCw/I/15143096510391.jpg
[15143103694077.jpg]: https://lh3.googleusercontent.com/-yiG-0l_kaJQ/WkL2h0uQaxI/AAAAAAAAAYc/ftIaQYwJFFQyhbvz8SCiFYgyXB0D2m47ACHMYCw/I/15143103694077.jpg
[15143107192194.jpg]: https://lh3.googleusercontent.com/-QXq_bU7lfGc/WkL2iLGl9hI/AAAAAAAAAYg/yyGjakIrAlY4zZ6SeSk90NFE0Pe3hOG3QCHMYCw/I/15143107192194.jpg
[15143108890619.jpg]: https://lh3.googleusercontent.com/-d2BzAo8aED4/WkL2iZuaaQI/AAAAAAAAAYk/RQtxaFodkpAvlWfJ3PXzPl7IaG-ciGutQCHMYCw/I/15143108890619.jpg
[15143111824852.jpg]: https://lh3.googleusercontent.com/-MXM35xD1GGs/WkL2iiDL11I/AAAAAAAAAYo/zurLECppN2kmuBm1e-LjCTIkF1-ELdftwCHMYCw/I/15143111824852.jpg
[Center]: /images/20220602/76989be83b424dd689db1f4927314d05.png
[15143344438019.jpg]: https://lh3.googleusercontent.com/-6Gc0SusjMwo/WkL2i2YZCAI/AAAAAAAAAYs/hXldSvn24rQxQuNOY70J_E7fXt0rOuJwwCHMYCw/I/15143344438019.jpg
[15143344921317.jpg]: https://lh3.googleusercontent.com/-AG7nsSOAfXE/WkL2jCkzMFI/AAAAAAAAAYw/cuBFiJDwARoe4Oe7p2aNNXuSmrHddGfxgCHMYCw/I/15143344921317.jpg
[15143360745284.jpg]: https://lh3.googleusercontent.com/-fV_sCDlijFw/WkL2jdMhNxI/AAAAAAAAAY0/uOaUUmH9_7k-KGugB6to9AC1Sc9R2T10wCHMYCw/I/15143360745284.jpg
[15143366288510.jpg]: https://lh3.googleusercontent.com/-QU7hznGq7-s/WkL2jksSoiI/AAAAAAAAAY4/Sjeenz7pC5sWikKTxwk-_9Y5S8Hl7neLwCHMYCw/I/15143366288510.jpg
[15143366909082.jpg]: https://lh3.googleusercontent.com/-8Np-RMElUJA/WkL2j-2DPcI/AAAAAAAAAY8/yWw2V4w8978ne4mLJURT74Na6OPaqJ4wACHMYCw/I/15143366909082.jpg
[15143373607895.jpg]: https://lh3.googleusercontent.com/-Vkk9K8dsFKU/WkL2kKO2v_I/AAAAAAAAAZA/kXVjeYdBkn0MFU71a6VCe7oQE0gMCGJIACHMYCw/I/15143373607895.jpg
[15143375710754.jpg]: https://lh3.googleusercontent.com/-hCTirhq-0LM/WkL2kaNdopI/AAAAAAAAAZE/1-MWKIpMePoWPweVPHnrEJo_17USbApBACHMYCw/I/15143375710754.jpg
[Link 1]: http://15721.courses.cs.cmu.edu/spring2017/slides/10-storage.pdf