如何自己实现一个关系型数据库？
https://www.zhihu.com/question/38870156
作者：robert
链接：https://www.zhihu.com/question/25405073/answer/138210064
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
Database System Concept 和 Database System Implementation 是两本不错的书，但是大家好像只提到了书，却没有说该怎么做。写一个数据库，路径的选择很重要，否则很容易放弃。推荐这样的路径：
1. 数据库是一个后端server，因此网络通信，如何并发处理多个客户端连接，收发数据，是首先要解决的问题。这个问题比较简单，不再赘述。
2. 数据库最基本的工作模式，是接收并理解一段代码，根据这段代码的逻辑，往服务器上写入/读取一些数据。因此，最基本的模块有两个，一个是代码的解释和执行， 一个是数据存储。
a.sql的解释和执行，可以用lex&yacc简单写一个语法解析器，一段sql发过来能够正确转换成内部结构体；再围绕这些内部结构体，写出语义分析代码，最终将sql转换成对存储模块的调用。
b.存储模块，除了设计好供上层调用的API，重点解决两个问题：1. 构建B树，管理一张表的数据； 2.将整颗B树持久化到磁盘/从磁盘中读取B树数据。一般的做法是一个B树节点对应一个数据块，一个数据块对应多条记录，以及相邻B树节点的数据块地址。 以数据块为单位写入，读取。为优化数据库的读写性能，需要在设计缓存和日志模块，将数据块缓存到内存，作为读取操作的缓存；日志则用来优化磁盘数据写入，将写入数据块时的随机写磁盘，转换为写日志的顺序写磁盘，如果宕机能够根据日志恢复数据块。在保证数据持久化的同时提高磁盘写入性能。
c.存储模块写好后，还需要一个元数据模块，来描述各数据块对应的库表，和数据库中记录的语义。简单的做法，可以把业务表的定义放在配置文件中，系统启动后即加载配置文件，将库表定义放入内存，用来解释数据块内容；如果还要支持DDL，即根据SQL语句创建/修改表结构，则可以从create table这条sql的实现入手，去构建元数据的管理模块，一方面做到根据元数据解释数据块；另一方面做到将元数据持久化。
3. 事务支持。事务这套理论，用来解决多用户并发操作相同库表时，操作的一致性问题。理想的情况下，数据库系统最终需要让多个并发操作的结果，能够等同于将这多个操作，进行某种串行排列后执行的结果，即并发操作的可串行化，但是实际上达、做到这一点成本很高，数据库系能会很差，所以事务理论定义了4种隔离级别，对一致性做了一些妥协，来保证并发读写性能。单机数据库下，事务机制不管从理论还是实现，都已经非常成熟，但要做好并不容易。
如何设计并实现一个 DBMS？
https://www.zhihu.com/question/25405073
实现简单的sql增删改查应该可以用python实现的。不过语言只是工具，原理才是根本，我觉得了解简单的DB结构还是必要的。
1. 数据库文件的组织形式，包括数据文件和索引文件。一种是将数据，索引分离存储（MyISAM），另一种数据库文件本身就是按B+树组织的，也就是数据和索引是同个文件（InnoDB）。
2. 数据库文件的结构：一般按page或block组织，一个block 4k大小。SQLite的数据表就是由一个或多个page构成。
3. 数据库系统结构：可以参照SQLite的系统结构，将系统分为Front-end前端，和Back-end（后端）。
Front-end：SQL的解析器，将输入的sql命令进行tokenize，然后对sql语法进行parse，转化为内部命令格式（后端调用）。
Back-end：要负责catalog的管理，增删改查record时要建立index，也就涉及page/buffer管理。
4. 具体实现：如果不考虑事务，并发，复杂的sql操作，可以参考下面的实现模块。
作者：陈炳金
链接：https://www.zhihu.com/question/38870156/answer/80538773
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。