最近打算通过手写一个数据库的方式，来达到掌握数据库的原理的目的，同时，以此为脉络，把数据库设计涉及的一些知识形成脉络，另外还对自己的薄弱的知识块进行查漏补缺，从初级开发到高级开发那些短板都能补齐。也不好承诺一周能拿出多少时间去做这个事情，毕竟身后已满是旗帜（flag）。一步步来吧，万丈高楼平地起嘛。

这篇笔记属于知识脉络梳理的，一方面可以让知识系统化，另一方面可以细化任务，让学习的目的和方向更清晰，更可控。

stanford CS346

stanford CS346 课程作业是实现一个简单的数据库系统，具体拆分为以下几步：

  1. RM（record manager 数据管理）

  2. IX（index system）

  3. SM（system manager）

  4. QL（sql 查询语言实现）

  5. EX（选一个方向然后实现）

这篇笔记算是对RM和IX的抛砖引玉。

数据库的诞生和发展

鲁迅说过，计算机主要完成两件事：计算和存储（鲁迅：那是周树人说的与我何干）。翻阅图灵奖的历史，至今有四位图灵奖获得者因为在数据库领域的杰出贡献而获奖，足以见得，数据库诞生的重要意义。

1956年，在计算机诞生将近20年的时候，IBM公司成功推出磁盘存储方案，相较于在那之间的磁带技术，磁盘支持随机读取，容量大，计算机开始逐渐活跃在数据处理领域。最开始，数据处理软件只有文件管理，后来出现了文件系统，但是磁盘的数据冗余问题非常严重，据说阿波罗登月计划用的磁盘有60%以上是冗余数据，后来，一个老家伙倒腾出了网状数据库，并且于1971年推动CODASYL提出了DTBG模型，直接影响了后续的数据库技术，同年，unix的缔造者们开始撸unix-kernal，数据库的诞生完全和操作系统是同时进行的。

注意，数据库最初的诞生完全是为了解决磁盘数据冗余的问题！！所以wangyin在关系式模型的实质对数据库和关系模型的吐槽显得站不住脚，当然不是说他说的东西有问题，他说关系模型表现力不如基础的数据结构，说查询语言，sql，cyber之类的不如普通的编程语言，这当然是在扯淡了。

  1. 关系模型只能等价于别的数据结构，比如用关系模型去模拟1:1/1:m/n:m关系都是ojbk的。
  2. sql，cypher之类的语言本身是图灵不完备的语言，编程语言基本上都是图灵完备的语言，表现力不足不是板上钉钉的吗？

用今天的观点去看待历史，批评数据库，关系模型，何不食肉糜？

数据库和文件系统

CS346在RM一节中的任务主要介绍了

1
2
3
4
5
6
7
8
9
10
11
12
13
class PF_Manager
{
  public:
       PF_Manager    ();                           // Constructor
       ~PF_Manager   ();                           // Destructor
    RC CreateFile    (const char *fileName);       // Create a new file
    RC DestroyFile   (const char *fileName);       // Destroy a file
    RC OpenFile      (const char *fileName, PF_FileHandle &fileHandle);  
                                                   // Open a file
    RC CloseFile     (PF_FileHandle &fileHandle);  // Close a file
    RC AllocateBlock (char *&buffer);              // Allocate a new scratch page in buffer
    RC DisposeBlock  (char *buffer);               // Dispose of a scratch page
};

数据库和树

参考资料：

《图灵和ACM图灵奖》