实现数据库 - 如何开始

Question

我一直在努力学习编程.我研究过Java和Python,我对它们的语法很满意.最近,我想利用我从头开始编写有形软件所学到的知识.

我想实现一个数据库引擎,一种NoSQL数据库.我整理了一个小文档,在我编写代码的过程中遵循的规范.但我所知道的只是一堆关键词.我不知道从哪里开始.

有人可以帮我找到如何收集这种工作所需的知识以及学习东西的顺序吗？我搜索了文档,但我觉得我最终会找到无关/错误的内容或从错误的点开始,因为实现一个完整的数据库引擎(似乎是)一个真正复杂的任务.

我不想表达我更喜欢论文和白皮书以及(e)书籍到其他项目的代码,因为我已经问过一个人们通常会以"阅读项目 - x"的形式得到回答的问题.源代码".我没有达到舒适阅读和理解源代码的水平.

Answer 1

首先,您可以查看如何编写简单数据库引擎的答案.虽然它专注于SQL引擎,但答案中仍然有很多好的材料.

否则,一个好的项目教程是B树数据库类的实现.示例代码是用C++编写的,但是对于完成的内容和原因的描述可能是您想要查看的内容.

此外,还有在MSDN上设计和实现结构化存储(数据库引擎).那里有大量的信息可以帮助你学习你的学习项目.

Answer 2

因为接受的答案只提供了与其他资源的(良好)链接,所以我认为我分享了编写webdb这一浏览器的小型实验数据库的经验.我还邀请您阅读源代码.它很小.您应该能够通读它,并在几个小时内了解它正在做什么.警告:我是一个n00b,因为写这篇文章后我学到了很多东西,看到我做错了.它可以帮助你开始.

基础知识:BTree

我开始调整AVL树以满足我的需求.AVL树是一种自平衡二叉搜索树.将密钥K和相关数据(如果有)存储在节点中,然后将所有项目存储key < K在左子树中的节点中,将所有项目存储key > K在右子树中.如果要支持非唯一键,可以使用数组存储数据项.

这个树将为您提供基本知识:创建,更新,删除以及通过键快速获取项目的方法,或者键<x的所有项目,或者x和y之间的键等.它可以作为我们表格的索引.

架构

作为下一步,我编写了允许客户端代码定义模式的代码.类似的方法等createTable().模式通常与SQL相关联,但即使没有-SQL排序也有模式; 它们通常要求您标记ID字段以及要搜索的任何其他字段.您可以根据需要使您的架构变得更加精美,但是您通常希望至少建模哪些列作为主键以及哪些字段将经常搜索并需要索引.

创建数据结构以存储表

我决定使用我在第一步中创建的树来存储我的项目.这些是简单的JS对象.定义了哪个字段包含PK后,我可以使用该字段的值作为键将项目插入树中.这使我可以通过ID(范围)快速查找.

接下来,我为每个需要索引的列添加了另一个树.在这些树中,我没有存储完整记录,只有密钥.因此,为了通过姓氏获取客户,我将首先使用姓氏上的索引来获取ID,然后使用主键索引来获取实际记录.我之所以不存储(引用)实际对象的原因是因为它使得set操作更简单一点(参见下一步)

查询

现在我们有一个包含PK和搜索字段索引的表,我们可以实现查询.我没有采取这一点,因为它很快变得复杂,但你可以通过一些基本功能获得一些不错的功能.WebDB不实现连接; 所有查询仅在单个表上运行.但是一旦你理解了这一点,你就会看到一个非常清晰(虽然漫长而曲折)的连接路径和其他复杂的东西.

在WebDB中,要获得所有客户firstName = 'John'并且city = 'New York'(假设这是两个搜索字段),您可以编写如下内容:

var webDb = ...
var johnsFromNY = webDb.customers.get({
  firstName: 'John',
  city: 'New York'
})

为了解决这个问题,我们首先进行两次查询:我们得到名为"John"的所有客户ID 的集合X,我们从纽约获得所有客户ID 的集合Y. 然后,我们在这两组上执行交集,以获得所有来自纽约的名为"John" AND的客户ID .然后,我们运行我们的结果ID集合,获取每个ID的实际记录并将其添加到结果数组中.

使用联合和交集等集合运算符,我们可以执行AND和OR搜索.我只实现了AND.

执行连接(我认为)涉及在内存中创建临时表,然后在查询与连接结果一起运行时填充它们,然后将查询条件应用于临时表.我从来没有到过那里.我接下来尝试了一些同步逻辑,但那太野心了,从那里开始走下坡路:)