高级数据库理论要点

备用知识：

一个数据库被映射到多个不同的文件。每个文件分成定长的存储单元，称为块。块是存储分配和数据传输的基本单元。一个块可能包含很多条记录。
内存数据库和传统数据库：传统数据库适用于处理永久、稳定的数据；内存数据库适用于处理实时性较强的逻辑业务数据。

1、存储：了解在磁盘数据库变长类型的原因、分析和解决，如果将磁盘数据库改为内存数据库，又将怎么样？

原因：个人认为是节约空间的一种手段。（比如一篇博客可以是好几千字，也可以是几十个字，这样定长考虑最大范围之内就很浪费空间了）
分析：变长记录出现的方式主要有三种情况：1）多种记录类型在一个文件中出现；2）允许一个或多个字段是变长记录类型；3）允许可重复字段的记录类型；
存储时应该解决的两大问题：如何描述一条记录使得单个属性可以轻松抽取？在块中如何存储变长记录使得可以轻松抽取？
解决：将变长记录分为两个部分：定长和变长属性；记录前面存储定长属性，后面存储变长属性，在每个变长属性前面维护一个槽目录（偏移量：该字段存储距离记录头的相对位置，长度：该字段的长度），已知一个磁盘块存储记录时，记录本身是从后往前存储，而目录是从前往后存储，这样的好处就是变长记录不需要用到的空间可以利用起来存储其他内容，对于记录的更新（考虑变长），若变长，前面存储的内容往前推移，类似插入操作。由于每个块大小只有4KB~8KB，所以效率影响不大。

对于内存数据库，阅读了两篇关于内存数据库存储的硕士论文：内存数据库是按照字节/字偏移存储，而磁盘数据库是块设备，两者存储区别较大。所以内存数据库对于记录的定长或者变长存储区别不大。内存数据库比较关注共享内存的问题，存储结构大致分有三种：位图法（和磁盘数据库的位图法类似）、内存池（划分多个不同的定长块）、区段式数据组织结构（每个记录记为一个三元组<分区号，段号，段内记录号>，这种用得比较多）。对于每个页内记录的存储两种方式：N-Array（水平式，一行一行存储记录）和离散式（垂直式，一个记录存储在多个页中）。

区段式数据组织结构参考图

2、内存数据库：定义、分类，以Redis为例说明如何解决持久化和持久化的实现机制？

定义：设有数据库DB，TA是数据库DB所有事务的集合，D(T)是任一事务T的操作数据集，且有任一时刻事务T属于TA，DBM(t)是 t 时刻在数据库DB内存中的数据集，而WT(t)是 t 时刻TA的活动事务集。若任一时刻，当事务T属于WT(t)，有D(T)属于DBM(t)成立，则称数据库DB为内存数据库。

以上是内存数据库的定义，简单来讲就是对于任一时刻，数据库中的数据和相应事务都在内存中。

分类：分全内存计算和热内存计算。全内存计算，即数据需要全部装载到内存中进行计算，对硬件要求高。热内存计算，部分数据加载到内存中即可以进行计算，硬盘和内存会有数据交换来计算未加载的数据。
解决持久化：
两种模式：不定期通过异步方式保存到磁盘（持久化模式）和每一次数据变化都写入一个AOF[append only file]里面（全持久化模式）
1）快照，将内存中的数据以快照（可设置n秒内如果超过m个key变化自动快照）的方式存入二进制文件中，注意是全部数据写入。过程：fork()父进程继续运行，子进程负责写入数据。
2）AOF：将每一个收到的写命令都通过write函数追加到一个文件中。当redis重启时会通过重新执行文件中保存的写命令来在内存中重建整个数据库的内容。

3、索引：顺序索引原理，插入、删除操作具体。

顺序索引原理：
搜索码：用于在文件中查找记录的属性集。索引码上有聚集索引的文件称为索引顺序文件。索引项由搜索码值和指向具有该搜索码值得一条或多条记录的指针构成。
顺序索引：基于值得顺序排序。
可以分为主索引（记录文件按照某个搜索码制定顺序排序）和辅助索引（搜索码指定的顺序和文件记录的物理顺序不同）
也可以分为稠密索引（每个搜索码都有一个索引项）和稀疏索引（部分搜索码的值由索引项）

举个简单例子：

索引更新伪代码：（以上图稠密索引为例子下图说明）
插入：
if （搜索码值不在索引中）{
    合适位置添加搜索码值索引项；(a)
}
else {
    if （索引项存储的是指向所有具有相同搜索码值的记录的指针） {
        添加一个指向新纪录的指针；(b)
    }
    else {
        把待插入的记录放在具有相同搜索码值得其他记录之后；(c)
    }
}
删除：
if（特定搜索码值得唯一一条记录） {
    删除索引项； （d）
}
else {
    if (索引项存储的是指向所有具有相同搜索码值的记录的指针) {
        删除指向记录的指针；  (e) 
    }
    else{
        更新索引项，使指向下一条记录； (f)
    }
}

插入：

删除：

4、查询：分析嵌套循环、块嵌套循环、哈希连接、归并连接计算两个关系R和S之间磁盘查询开销。

了解数据库、磁盘、内存之间读写关系：

主要理解算法思想：
嵌套循环：两层for循环，对于外循环每个块中的每条记录都要一层for内循环；
块嵌套循环：两层for循环；
哈希（散列）连接：使用散列函数对两个关系相同属性集进行哈希，不同关系的哈希值相同的项进行连接；
归并连接：先对两个关系中相同属性集排序，两个指针分别指向两个关系中相同属性集的集合遍历连接。

辅助理解：
哈希连接：

举个例子：
假设R有5000条记录，磁盘块数100；S有10000条记录，磁盘块数400，最坏情况只有两块缓存,分析复杂度
嵌套循环：5000 * 400 + 100 + （5000 + 100）
块嵌套循环：100 * 400 + 100 + （2 * 100）
哈希连接：影响因素主要是散列函数的设计
归并连接：（这里不讨论排序代价）100 + 400 + （400 + 100）

5、时态数据库：定义、分类，每个分类中时间扮演的角色和作用；利用SQL2011时态数据库的语法完成DDL和DML操作，用表格表示结果操作。

定义：存储关于真实世界的时间经历状态的信息的数据库。
分类、时间的角色和作用：
历史数据库（数据库中被管理对象的生命周期是对象的有效时间，每一个元组记录了数据的一个“历史”状态）；
回滚数据库（数据库中被管理对象的生命周期是事务时间的数据库）；
双时态数据库（数据库中元组包含一个系统支持的有效时间和一个系统支持的事务时间的数据库）。

SQL:2011语法标准参考：http://blog.itpub.net/31544289/viewspace-2157766/

6、认识NoSQL。

参考：https://www.cnblogs.com/lina520/p/7919551.html
定义：非关系型的数据库。
代表：Redis（支持多种数据结构，支持持久化操作，单线程请求，可以用来进行消息订阅与通知），Memcache（可以利用多核优势，单实例吞吐量极高，可以达到几十万），MongoDB（更高的写负载，处理很大的规模的单表，高可用性，快速的查询）；
三者的性能都比较高，总的来讲：Memcache和Redis差不多，要高于MongoDB

参考文献：
[1]蒋智鹏. 内存数据库的存储管理[D].华中科技大学,2008.
[2]胡志强. 内存数据库存储分析与设计[D].北京邮电大学,2011.