数据库数据存储结构

Database System Concepts 13th Data Storage Structures 学习

许多数据库以操作系统文件作为中间层来存储记录，数据会被写到文件中，文件被持久化到磁盘。

数据库会被map到多个文件存储到底层磁盘上。一个文件包含多条记录。
每一个文件在逻辑上也被分成固定长度的块（blocks,也叫做Page）,一个块通常4~8k。
一个块中会包含多条记录（特别长的记录可能会超过一个块的大小，一个记录可能会跨越两个块，一般不允许记录跨Page存放，因为处理起来太复杂。所以一个Page并不是100%都存放数据行的，有一些剩余的空间就被浪费掉了）

那么第一个问题来了，一条记录（或者说数据库中的一行）在文件中怎么存储（存储格式）？？？？

Fixed-Length Records （定长记录）

定长记录最好组织，因为每个列都是固定长度，每一行分配固定长度的字节数就行。

例如：

type instructor = record
    ID varchar (5);
    name varchar(20);
    dept name varchar (20);
    salary numeric (8,2);
end

假设 varchar 按最大长度分配空间， numeric 暂用8个字节。这样一行暂用 53个字节。这样可以用最开始的53字节存第一行，下53个字节存储第二行，以此类推。

fix-length.png

但这样如果删除了一行怎么办，我们怎么回收被删除行所暂用的空间？？？？

1. 删除记录后面的行依次往前移动，但这样会涉及大量数据的移动。
2. 用一个链表把删除的行串起来，加一个头结点指向第一个被删除的行，这样插入时可以从头结点往后找插入位置。

shanchu.png

Variable-Length Records （变长记录）

变长记录像包含 varchar(2000) 的怎么存呢？？？

有两个基本问题需要考虑：

1. 一条记录我们要能方便的提取出每一列的数据。（定长的很好提取，因为每个列长度是固定的，很好分离）
2. 在一个block中我们要能快速的提取每一条记录（定长的也很好定位，因为每一行占用的字节数是固定的）

一行中一般既有定长的列又有变长的列，定长的列我们可以按顺序依次放在记录的开头，变长的列用一个 (offset, length) 元组来表示（例如每个元组用4个字节表示），这些元组也放在记录的开头。
定长的列和 offset 元组组成记录的定长部分存储在记录的起始部分，起始部分之后存储变长列的数据。

variable-length.png

这个图很好理解，多看几遍就明白了

Null bitmap 顾名思义，是用来表示某一列值是否是 null 的。 instructor 只有4个列，所有用一个字节就够了。（一个列用一位表示，如果某列的值是null则相应的位置为 1）

现在解决了第一个问题，单个变长记录的存储格式。通过 (offset, length) 可以轻松的分离出各个列。
看第二个问题，多个变长记录在block中怎么存储？？？？

业界也有成熟的解决方案，用的比较多的是 Slotted-page structure

slotted-page.png

Block Header：一个块的头里面存储：

1. 这个块中有多少个记录
2. 可用空间的末尾位置（ end of free space in the block）
3. 一个指向各个记录的指针数组，数组中每一项存储一个记录的位置和该记录的长度

一个空的block 开始插入时第一个记录存在 block 的末尾， 同时在Block Header 中的数组加一项指向这个记录。第二条记录接着往前存，以此类推。 可用空间被夹在了中间部分。

删除一个记录怎么办？？？

删除一条记录直接回收它所暂用的空间，指针数组中把它标记为已删除（如可以把它的 size 设置为 -1）。它前面的记录依次往后移动， 同时 header 中的指针数组也要相应的更新。因为一个 block 4~8k，这个移动并没有太大影响。

Slotted-page 要求所有的指针不能直接指向记录本身，只能指向header 中指针数组项（二级指针）。这样记录移动时，引用该记录的地方不需要改变。

Storing Large Objects（大对象）

BLOB， CLOB 怎么存储？？？
LOB 就是 Large Object 的缩写， BLOB 是二进制大对象，如图片，视频。CLOB 是字符大对象，如 Text 长文本。

1. 大对象如视频可以不放在数据库中而是放在文件系统中，数据库中只存储路径。
2. 视频等也可以直接存到数据库中，很多数据库会把大对象放到单独的blocks(一个或多个)中去，相应的列用一个指针指过去。

Organization of Records in Files （文件中记录的组织）

记录在文件中怎么组织呢？？？？

1. Heap File Organization：
   就是记录可以存储在文件中的任何位置，没有什么顺序。
   怎么在文件中找到一个可用的块呢？？？很多数据库用 free-space map （用一个map结构维护各个块的使用情况）来跟踪各个块可用空间的大小。

2. Sequential File Organization
   按顺序存储，如按主键 ID 递增的顺序存储。但当删除和更新时要维护这个有序性代价很高。

3. Multitable Clustering File Organization:
   通常一个表 (relation) 的数据只存储在一个文件中（或多个），Multitable Clustering 是说多个表的数据可以混杂存储在一个文件中。
   这样有什么好处呢？？？ 混在一起存单独查询不还得分离吗？？？？
   对于特定场景混在一起存可以提高效率，如 join 操作等。

4. B+-tree file organization

B+ 树不是索引结构吗？？？ B+树是索引结构啊， 为什么把记录按B+ 树的结构来组织？？因为查询效率高啊。 B是 balanced 的缩写，B+树是一颗平衡树。
一条记录可以存储在B+树的叶子节点中。这不是白白浪费了很多空间吗（B+树中间结点不存储数据只存储指针），为什么这样？？？
是浪费了很多空间，索引还不是为了快速查询。没有索引虽然省了一点点空间，但每次查询都得全表扫描。就像一本书如果没有书签你就得一页一页的翻，如果有书签直接跳过去就行了，虽然浪费了几页纸存书签。

Database Buffer：

什么是 Buffer , buffer （缓存）就是内存中的一块区域。专门用来缓存磁盘块中的数据。为什么要缓存？ 提高效率啊， 每次都访问磁盘肯定非常慢，我们就把一部分磁盘块的数据 load到 buffer 中， 增删改查都是操作 buffer 中的块， 更新的块再异步的同步到磁盘中。

如果一个请求的块没有在 buffer ,要先从磁盘中把相应的块加载进 buffer 再操作 buffer。
如果所有的buffer 都被暂满了，这时还要从磁盘加载新的块怎么办？？？ 这时就要找一个块置换回磁盘，选哪个块置换呢？？？ LRU 是一种策略（把最近一段时间操作最少的块换出去，写回磁盘）。

这不跟虚拟内存一样吗， 确实差不多！！！