Data Representation & External S

数据表示

数据如何存储在存储设备(硬盘)上

一般的，关系型数据库中，数据都是以一行一行的记录进行存储和表示，例如在MySQL中，每一行代表了一个记录，其中包含了一些字段，每一个字段分别有其对应的数据类型

具体的说，在初始建立schema的时候这些被确定，例如：

Relational database elements:
CREATE TABLE Product (
pid INT PRIMARY KEY,
name CHAR(20),
description VARCHAR(200),
maker CHAR(10) REFERENCES Company(name))

字段的存储

对于一条记录而言，其内部的字段存储按照顺序排列如下：

字段存储（1）.png

每一个字段有其自身的schema，例如数据类型和长度，这些也是记录，被保存在system catalogs，对于MySQL来说，这些元数据就被保存在information_schema数据库中

但是要注意，字段可以是可变长度的，这个时候一套固定长度排列就对记录的存储不起作用了，所以在存储每一条记录的时候，会有一个记录头，存储该条记录的一些元数据信

一般的，记录头中会有如下信息：
• Pointer to schema: help finding fields
• Length: so we know where the record ends without consulting schema
• Timestamp: time when record last modified or read

字段存储（2）.png

这里默认的存储方式为
1.首先存储固定长度的字段
2.对于每一个可变长度的字段，记录头中有对应的pointer指向这个字段的起始offset

记录的存储

对于每一条记录而言，其最终被保存在硬盘的某个块中，其存储方式为：

记录存储.png

这样设计的好处有：
对于插入新的记录，其呈现一个从两边向中间索取free space来添加offset table和数据，不需要移动已有的数据。

不好的设计方式.png

外排序

如何解决在1GB内存上对1TB的数据进行排序

首先明确一点：计算机在执行一项操作的过程，其主要分为三部分
1.数据的输入 2.数据的处理 3.数据的输出
这里1和3就是IO过程，对于数据库而言，时间成本主要有IO造成。

一些notation：
Page: A block on storage devices loaded into a
page in main memory

Buffer pages: pages in main memory used to
store input, output, and intermediate data for an
algorithm

Run: a sorted sublist of input data

Pass: Loading the entire data from disk once

解释:
一般的，数据存储在硬盘的Block上，而对数据进行处理的话，第一步需要其读取到内存中，内存中数据以Page的方式进行存储（我们这里假设硬盘的一个Block和内存的一个Page一样大小），Buffer Pages可以认为是内存的容量，例如说其有3个Page，表示其最多一次可以读取3个page的数据到内存中，Run的含义表示通过内存对输入的数据进行排序处理后输出到硬盘中，其本质就是若干个已经排序好的Block，Pass表示对所有数据的一次读取。

二路归并

假设：
1.内存的容量为3个page，需要对硬盘中n个block的文件进行排序
2.读取数据过程中，内存读取一个page

2-way merge sort.png

Pass 0： Read a page, sort it, write it
其本质上是一个sorting过程，通过这一步操作将每个page变成一个有序的page

Pass 1, 2, …, etc.: merging two runs at a time
这里需要注意，由于是二路归并,所以需要3个buffer page，也就是说内存大小至少是3个page，其中2个buffer page作为input page，一个buffer page作为output page.
Pass 1, 2, …, 本质上是一个merging的过程

总的来说：

如果文件有N个page，那么需要pass的个数为
⌈log2N⌉ + 1
每一个pass，内存将文件的所有数据读取，然后处理输出到硬盘中（read & write），所以总的时间成本为
2N（⌈log2N⌉ + 1 ）

外排序

more memory -> use it to improve performance
• M: # of blocks (i.e., pages) in main memory 10
• B(R): # of blocks of relation R
Let's suppose M = 10, B = 100

从上面的二路归并，可以发现，在pass0的过程，并没有完全利用内存的存储，只是一次读入一个page进行排序，其实浪费了两个page的空间，所以对其进行改进：
Pass 0: load M blocks in memory, sort
Result: B(R)/M sorted sublists of size M，each sorted sublist is a run
这里我们从硬盘中读取M个block，进行排序，将生成的结果重新写入硬盘，所以对于一个100个block的文件，第一次读写可以得到100/10=10个有序的数据列表[A1,A2,....A10]

Pass 1:
Merge M – 1 runs into a new run
我们从二路归并了解到，内存必须要有一个output page作为输出，那么剩余的page都可以作为输入，所以对于有M个page的内存，其充分利用内存空间，可以进行M-1路归并，所以我们可以读取10-1=9个有序列表到内存中进行排序，注意这里的读取的意思不是一次性读进去。

关于读取的解读：
pass1可以读取M-1个有序列表，每一个有序列表Ai包含了M个page，所以其相当于排队，内存的M-1个page分别读取M-1个有序列表的第一个page，通过比较输出到output page中，然后再依次读取M-1个有序列表中未读取的page。
（有点绕。。文字功底比较差。。）

对于这样的输入输出，需要的pass数为
num = ⌈logM-1⌈B/M ⌉⌉ + 1
总时间成本 2Bnum

具体例子：
with 5 buffer pages, to sort 108 page file:
– Pass 0: produces 108/5= 22 runs (21 sorted runs of
5 pages each + last run of only 3 pages)
– Pass 1:
22/4 = 6 (5 sorted runs of 20 pages each +
last run or only 8 pages)
– Pass 2: 2 sorted runs, 80 pages and 28 pages
– Pass 3: Sorted file of 108 pages

4-way sorting.png