Storage
Tuple-Oriented Storage
在前面，我们初步了解了一种数据在底层的组织形式，在这里我们考虑一个问题，即使我们知道了一个数据的存在，我们需要怎么去找到这个数据呢？
第一想到的肯定得是构建数据的物理实际储存地址，在DBMS中，一个元组的物理位置被称为record ID，用于记录索引一个元组所必备的一些信息。
Record ID
这里需要注意的是，我们这里了解物理地址并不是为了去使用它，毕竟你也应该知道直接去使用一个东西的绝对地址是一个多么愚蠢的事情，我们需要的只是了解它，并在之后可能的应用场景中不至于犯下一些愚蠢的错误。
对于一个Record ID，其中会储存很多的信息，包括但不限于一些文件id,页的id,对应的槽的id。通过这样去逐层的索引到目标元素。
绝大多数的DBMS并不会在元组中去储存对于的id信息，毕竟这是没有意义的，你储存它对于你的外部使用来说没有什么意义，这东西应该有底层自动管理，暴露给外界的话还可能导致一些违法的操作而导致错误。(指的是显式储存)
从储存上来讲，假设确实有这些id信息的元组存在，那么你如果要去获取这些信息，你需要提前知道这些信息，那么你已经知道了你还要去用已知的再去寻找一遍，多少有点脱裤子放屁的意思了。我们完全可以通过DBMS的一些设置来给我们放回一些数据的物理位置而不是在元组中去额外添加属性进行标识。当然，这些只是一般情况，对于哪些实际情况，当我没说。
在一些DBMS中，提供了一些能够返回Record ID的方法，在postgres中可以对于输出的属性去读取其的隐藏属性ctid去读取对于的id信息。对应的是一个二元组(x,x)第一个是对应的页编号，第二个是对应的槽编号。
在这上面的demo中可以看到在删除后另外俩个的ctid并没有发生变化，因此可以猜测这里的数据库实现应该是没有一个简单删除后进行一个自动合并的，或者说，这种简单的更改不会触发对应的合并程序(如果有的话)。
至于在各个系统中到底是一个怎么样的，可以自己搓一个表丢些数据进去再查查对于的地址看看嘛。
猜想
对于一个DBMS来说，我们通常可以通过系统内的方法去对于一个元组的record ID去进行获取，我猜测，这里的record ID只是在输出是由底层的一些数据整合出来的，实际上并没有这个属性在元组中。
工作方式
接下来我们来看到元组的操作(插入和删除)到底是一个什么个情况。
当我们需要插入一个新元组的时候。首先去查询页的词典去寻找一个带有空闲槽的页面(这个槽应该能够容纳带插入的数据)，接下来看写入磁盘的部分。
首先其会通过record ID去知道对应的页信息，然后通过我们的页索引表去找到对应的页，这里可能会出现页不再主存中的问题，此时会像程序执行时遇到段错误一样，先去吧对应的页调到主存中。接着再从元组的索引(之后会遇到的)中去提取对应的槽的位置，然后通过页内的槽的详细信息去找到页的具体偏移位置去进行操作，如果此时该位置的大小允许我们的操作，那么它将会直接在该位置上进行操作。
缺陷
接下来我们来看到这种面向元组储存的方式所存在的问题
- fragmentation（碎片化）对于使用槽页面和元组直接储存的结构来说，在不断的插入删除操作之后，页内的空白碎片可能越来越多且大小可能不一，当进行压缩后这种问题才能得到缓解，但是这种压缩操作又是非常耗时的。这种无法充分利用空间的缺点很令人恼火。而且，即使我进行了压缩，我们前面提到了页内是当槽数组与元组接触到之后被判定为满的，但是当我们剩余的空间无法储存接下来的数据时也会被判定为满，这种会导致在一个页在充满时总还是存在着一些空余的空间。
- Useless Disk I/O (无效的磁盘I/O) 这个问题前面讲到过，当我们需要去读取一个元组数据时，由于对于数据库来说，读取数据的基本单位是页，因此无论是读取多少个数据，都需要读取对应的整张页。这就意味着每次读取一个数据可能会导致大量的性能损失，就跟CPU所使用的缓存发生缓存未命中时的情况一样。
- Random Disk I/O(随机访问导致的磁盘I/O) 当我们更新数据时，由于元组数据在插入时遇到的情况不同，我们的一个更新语句可能会涉及到一个表中的多个页，这会导致在更新完一个元组后需要去到另外的页中进行更新，这将导致一个简单的更新操作都需要读取多个页，简单来看这就是比上面更加严重的缓存未命中情况。
扩展(我也不知道也不应该这么说)
在一些DBMS中，对于底层中的数据，其并不允许对于已有的数据进行修改，允许对于页进行插入操作，但是不允许修改已经存在于页中的数据。这种想法其实很简单，或者说之前也见到过，就是不要去动已经能够运行的代码。对于已经存在的数据进行修改的话，首先可能由于变长域的存在，这种修改可能会犹豫内存不足而失败，如果成功，那可能导致更为严重的问题，类似于语言中内存访问导致修改意料之外的数据的问题。因此，有些DBMS是不允许对于已有的数据进行修改的，当我们想要进行修改时，其可能对于整个内存页都会进行一个拷贝，并在这个页的拷贝中去更新对应的数据，在之后更新对应的索引和删除原来的页来实现。
有了这种情况对于上面提到的第三点其实也更能理解其所带来的性能损耗能有多么严重。
总的来说，这种架构的问题很简单也很严重，其一就是由数据插入本质导致的内存浪费问题，其二就是读取数据操作本质导致的缓存未命中而导致的性能损失问题。这种对于I/O的严重浪费是我们不想看到的，接下来看到DBMS的应对策略（有一说一，CMU中对于这些的引入真的是一种水到渠成的感受啊）。
Log-Structured Storage
在日志结构储存着部分中，我们将会致力于前面提到的三个问题。
首先，对于一个日志结构的储存，其调到主存中的内容还是于之前一致的，都是最近一次，也就是最新的table，在这个表中，元组数据可能被组织为一些特殊的逻辑结构，就假设是最简单的树形结构。当我们需要对其进行插入删除等操作的时候，这个表所做的可能是插入一个对应的节点，这个节点中储存了最新的操作之后的数据。
在之后的一定时机（一般就是在主存中的这个表满后），DBMS将会根据这个MenTable中的数据去构建该次操作中的SSTable表，需要注意的是，这个表中储存了所有的原先的表中的数据以及这次进行的操作以及各自对应的操作时机。但是对于SSTable来说，其只会使用这个表中最新的数据去进行构建最新版本的数据。
在产生一个SSTable后，OS会将其送回磁盘中去完成持久化储存。一般来说，在硬盘的储存结构上，新产生的SSTable会像栈被压入到对应表结构的level中，该类结构中一般为较新的结构越靠近压入口。在对应的一个层级level被压满时，此时会触发一种合并机制，将该层级的多个子表合并为多个大表并压入更深一层level进行储存，一次递归。层级越深，单个SSTable的大小越大，同时储存的信息所存在的时候举例现在越久。
同时，在单个层级中，SSTable的储存也存在着一定的时间次序，如果单单以上面的那种结构来看，从左到右的数据更新的时间举例现在越短，这种时间的有限顺序与物理储存顺序间的关联是有意义的。通过这种简单的映射，在进行合并时，我们能够选择有限合并更新时间相差不大的几个SSTable，只需要通过他们的相邻次序即可做到了。
我们来看一下在这种架构下存在着什么优点。对于数据库的操作，其中的读取操作其实还是没有什么较大的区别，主要在于写回的时候
- 在写回时，其中的操作并不会实时的写回，而是一种异步的状态，当主存中的表达到写回的接线是，对应的记录会被顺序的写入到一个新表中。这种顺序的操作比起之前那种随机读取的操作将要更加省时。
- 在disk的分层架构下，各个层级间的数据具有相对严谨的结构关系，这种层级架构可能使用某种特定的数据结构来实现（B+树）在索引这块也具有一定的加速作用。
当然，这种架构也存在着一定的问题，最明显的其实是在需要读取时它的性能消耗。
当我们查询一个操作时。首先，它会从当前磁盘中存在的表中去进行查找，如果存在，自然最好，如果不存在，那么就需要去在disk中去进行查找，对于每个SSTable进行二分搜索，最严重的情况是，它需要遍历所有的SSTable。
为了避免这种扫描全部的情况，添加了一种新的结构来进行优化
在添加了这种结构后，当需要执行一条查询语句时，首先去查询内存中的表是否存在数据，当不存在时，不会直接去磁盘中进行查找，而是先通过一个SummaryTable来进行一次过滤。
在这个表中，集合了每个层级中的键值索引来加速索引层级，储存了每个SSTable的最大最小码来索引哪个SSTable。
合并
在前面我们已经知道了当一个层级在容纳了一定量的SStable时，其会触发合并，我们接下来来看这个合并操作会是一个什么情况。
首先，需要知道的是，SSTable内部的记录是以一种有序的方式排列的，每条记录存在着其的键值。当我们需要进行合并时，对应的记录会根据所属的键值来进行合并，规则其实很简单，一个键值只要出现了，那么它就一定会被储存到新表中，如果一个键值在多个表中都存在数据，那么只保留最新的一条记录。
缺点
在这种架构下，由于表的合并操作，会导致DBMS出现一种写放大的缺点。
当一个SSTable被生成后，其会被送回到disk中，在disk中，其会检测现在是否需要去进行表的合并，并一次递归去检查所有的层级。在这种情况下，一个简单的表可能会导致多个层级都触发了合并操作，而且由于这些表都是位于disk中的，所以效率会相对较慢。相对来说，使用面向元组的普通结构就不会出现这种情况，那种每次写操作都有且只有一次进行了磁盘的覆写操作。
其实可以窥见，这之间就有这一定的利润可图，就比如网上的哪些提供远程数据库服务的平台，通常都是付费的，这是你给写操作，给硬盘损耗的一种必要付出，当然，这里说的还是很浅显，感兴趣就自己了解嘛。
接下来看到另外一种存储格式
Index-Origanized Storage
顾名思义，这是一种依托于索引的储存结构。所谓的索引，如果只在使用的角度上来看的话，其实可以看做是一种用于映射的结构，当一个输入通过一个索引的映射之后，我们将能够找到该块输入所需要的数据所在的位置，不同的DBMS存在着不同的索引实现。其中，可能是通过索引去找到数据所有的record ID进而去找到对应的储存结构去找到对应的数据的。当然，一种更优秀的方法时将每个数据组织为一种数据结构，就比如一颗树，每个节点具有一个特定的标识符，也就是所谓的索引，通过数据结构内的比较，实现对于一个数据的快速索引来加速查找。
简单来看上图中存在的树。在这种树结构的索引组织储存中。我们通常将树的节点划分为俩类，分别是Inner Nodes和Leaf Nodes,在Inner Nodes中，其只负责对应的输入索引接下来的路径，也就是说，当一个索引遍历运行到树上的某个节点时，节点上的某些信息回决定接下来遍历的节点的位置。一直遍历到叶子节点后停止继续深入查询。通常在树结构的储存中，叶子节点储存的是实际的数据（元组的集合，其可能是一个类似于槽页面的页面）。
这一个简单过了，等之后遇到B+树时再来进行分析。
小结
对于前面三种，我们来进行一下小结。首先需要明确的是，前面这三种结构本质上都是一个数据库对于其底层的数据的组织形式。
- Tuple-Oriented Storage（面向元组的储存）这种储存结构是指在储存数据时其的基本单位是一个元组，正如前面的槽页面。当使用这种储存结构时，我们需要储存的数据的基本单位是元组。
- Log-Structured Storage（面向日志的储存）这种储存结构相对来说每次进行查删改查的对象有了很大的变化，其不再像是之前按照元组储存的对于一个页来进行操作。其通过使用MemTable和SSTable来实现对于数据的读取和写入。
- Index-Origanized Storage（面向索引的储存）这种储存结构使用索引来构建出一种特殊的数据结构。这种数据结构上的每个节点通常都具有一定的信息，对于数据的操作可以等效为对于节点上的操作。
上面这三种数据组织结构的实用场景和优缺点在这里并没有列出，自己补充吧，接下来我们进入下一小节。
在前面，我们已经接触了三种数据的组织形式，接下来我们深入另一部分，元组的组织形式。
Tuple Storage
一个元组就是一段数据，其在底层上的表示就是一段01串，这并不难理解，但是也没什么意义，我们需要知道的是这一段01串内部的组织形式以及所具备的含义。
一个元组是一个字节序列，这一段字节序列上面通常带有一个头部来告诉你该段字节序列中的信息，一般为一个属性相对于该个字节序列的偏移量和该子字段的长度。如下图。
额外说明一下，对于一个字节序列，其一般会将一些定长字段放于该字段的前面，将变长字段分配与字段后部分。而且字段中的子字段的属性排序一般是与声明时的字段排序相一致的。
字节对齐
对于这些数据，正如C++中类的设计一样，为了方便CPU对于内存页的读取，这些数据通常存在着一定的格式上的限制，或者说，位上的限制。简单来说，如果允许一些乱七八糟的位排序，那可能会涉及到一些数据的跨页读取和处理，这是我们不想看到的，使用空间来换取一些时间是可以接受的。
正如之前CSAPP中看到过的情况一样，这种不符合64bit的格式布局其实很令人恼火，因为这会导致在读取时CPU需要去对于cdate进行一次跨字段的读取，而这通常需要俩次读取操作。当这种设计很频繁时，对于一个元组数据的读取，最差情况可能会恶化到优美排列的2倍。
要解决这种问题自然很简单，就像之前遇到过的一致，对于字节段进行一定的重排以及补充，使得其能够更加符合64位上的结构，就比如如果还是现在这种情况去填充字节，那么需要填充的字段可能需要多次，但是如果我们能够去进行一定的重排，使得各个小的字段去尽可能的凑成一个接近于64位的字段，我们就不必要去为每个字段都进行补齐，这在CSAPP中已经见过，简单了解即可。就比如下面这个demo
NULL
接下来讨论下对于NULL的处理。在数据库中，对于所有的域，都有着NULL值的存在，就设计上来看，我们一般不会像将这种空值设置为一种相对于其实值特殊的存在。虽然它特殊，但是特殊的只有它，为了这种值去额外设计一种麻烦的结构是我们不想看到的。运用设计模式的知识，我们会考虑通过一层缓冲来进行这种NULL值与其他类型的值的同化，这里有几种选择。
这块部分简单过一下即可。
- 使用一个空的位图头来进行标识，简单点说，就是设计出一个额外的结构来进行标识该元组的属性是否为空值，即课本中的空位图设计，这个看课本很容易看懂，略过。位于P311页处。
- 使用一个特殊值来进行标识，这种也很好理解，略过
- 为每个空值额外添加一个位来进行标识，但是这种事不推荐的一种做法，毕竟首先你就无法想象这种特殊化的操作会给后续的维护带来多大的麻烦，这种额外加了一位的操作会导致对齐以及解析方面的问题，很令人反感。