如何编写简单的数据库引擎

Question

如何编写简单的数据库引擎

a_m*_*m0d 140 sql database theory database-engine

我有兴趣了解数据库引擎的工作原理(即它的内部).我知道CS中教授的大多数基本数据结构(树,哈希表,列表等)以及对编译器理论的非常好的理解(并且实现了一个非常简单的解释器)但我不明白怎么去关于编写数据库引擎.我已经搜索了关于这个主题的教程,我找不到任何教程,所以我希望别人可以指出我正确的方向.基本上,我想了解以下信息:

数据如何在内部存储(即如何表示表格等)
引擎如何找到所需的数据(例如,运行SELECT查询)
如何以快速有效的方式插入数据

以及可能与此相关的任何其他主题.它不一定是磁盘上的数据库 - 即使内存数据库也没问题(如果它更容易),因为我只想学习它背后的原理.

非常感谢您的帮助.

Answer 1

Rob*_*vey 54

如果你擅长阅读代码,那么学习SQLite将教你一大堆关于数据库设计的知识.它很小,所以它更容易包裹你的头.但它也是专业写的.

http://sqlite.org/

我建议阅读SQLite 2.5.0的代码:https://github.com/davideuler/SQLite-2.5.0-for-code-reading,它是SQLite的早期版本,可以在现代GCC上编译和运行(我在MacOS 10.13和Debian 8上测试过它 (3认同)
sqlite下载shell.c => 3135,sqlite3.c => 136332,sqlite3ext.h => 447,sqlite3.h => 7097,总计=> 147011 (2认同)
https://cstack.github.io/db_tutorial/ 是一个很好的起点。 (2认同)

Answer 2

A.R*_*had 25

这个问题的答案很大.期望PHD论文能够100%回答;)但我们可以逐一思考问题:

如何在内部存储数据:你应该有一个包含数据库对象的数据文件和一个缓存机制来加载数据并将它周围的一些数据放到RAM中假设你有一个表,有了一些数据,我们会创建一个数据格式通过同意列分隔符和行分隔符的定义将此表转换为二进制文件,并确保在数据本身中从不使用这种分隔符模式.即,如果您已选择<*>来分隔列,则应验证您在此表中放置的数据不包含此模式.你也可以通过指定行的大小和一些内部索引号来使用行标题和列标题来加速搜索,并在每列的开头使这个列的长度像"Adam",1,11.1, "123 ABC Street POBox 456"你可以拥有它像<&RowHeader,1> <&Col1,CHR,4> Adam <&Col2,num,1,0> 1 <&Col3,Num,2,1> 111 <&Col4,CHR, 24> 123 ABC Street POBox 456 <&RowTrailer>
如何快速查找项目尝试使用散列和索引来指向存储和缓存的数据,基于不同的标准,采用上面的相同示例,您可以对第一列的值进行排序,并将其存储在单独的对象中,该对象指向按字母顺序排序的项目的行ID , 等等
如何加快我从Oracle知道的插入数据是他们在RAM和磁盘上的临时位置插入数据并定期进行内务管理,数据库引擎一直忙于优化其结构,但同时我们没有想要在电源故障的情况下丢失数据.因此,尝试将数据保存在此临时位置,不进行排序,附加原始存储,稍后在系统空闲时使用索引并在完成后清除临时区域

祝你好运,伟大的项目.

Answer 3

djn*_*jna 11

有关于这个主题的书籍,一个好的起点是数据库系统: Garcia-Molina,Ullman和Widom 的完整书籍

Answer 4

Jue*_*gen 10

以前提到过SQLite,但我想添加一些东西.

我个人通过学习SQlite学到了很多东西.有趣的是,我没有去过源代码(虽然我只是简短地看一下).通过阅读技术资料并特别查看它生成的内部命令,我学到了很多东西.它里面有一个自己的基于堆栈的解释器,你可以通过使用explain来读取它内部生成的P-Code.因此,您可以看到各种构造如何转换为低级引擎(这非常简单 - 但这也是其稳定性和效率的秘密).