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

我有兴趣了解数据库引擎是如何工作的(即它的内部结构)。我知道 CS 教授的大多数基本数据结构(树、哈希表、列表等) ，也非常了解编译器理论(并实现了一个非常简单的解释器) ，但我不知道如何编写一个数据库引擎。我已经搜索了关于这个主题的教程，但是我找不到任何教程，所以我希望其他人能够为我指明正确的方向。基本上，我希望了解以下方面的信息:

  • 数据是如何存储在内部的(例如，表是如何表示的，等等)
  • 引擎如何查找它需要的数据(例如，运行 SELECT 查询)
  • 如何快速有效地插入数据

以及任何与此相关的话题。它不一定是一个磁盘上的数据库——即使是一个内存数据库也可以(如果更简单的话) ，因为我只是想学习它背后的原理。

非常感谢你的帮助。

83104 次浏览
小开

有一些关于这个主题的书籍，一个很好的起点是由 Garcia-Molina，Ullman 和 Widom 撰写的 数据库系统: 全书

小开
最佳答案

如果您擅长阅读代码，那么学习 SQLite 将教会您一大堆关于数据库设计的知识。它很小，所以很容易理解。但它也是专业的写作。

用于代码读取的 SQLite 2.5.0

Http://sqlite.org/

小开

我建议大家关注 www.sqlite.org

这是最近的，小(源代码1MB) ，开放源代码(所以你可以自己弄清楚) ..。

有人写过关于如何实施的书:

Http://www.sqlite.org/books.html

它可以运行在桌面电脑和手机的各种操作系统上，所以实验很容易，学习它现在和将来都很有用。

这里甚至还有一个像样的社区: https://stackoverflow.com/questions/tagged/sqlite

小开

也许你可以向 HSQLDB学习。我认为他们为学习提供了小而简单的数据库。您可以查看代码，因为它是开源的。

小开

这个问题的答案是一个很大的问题。希望一篇博士论文能够100% 地回答这个问题;) 但我们可以一个接一个地想问题:

  • 如何在内部存储数据: 您应该有一个包含数据库对象的数据文件和一个缓存机制，用于将焦点中的数据和其周围的一些数据加载到 RAM 中 假设你有一个带有一些数据的表，我们将创建一个数据格式，通过同意列分隔符和行分隔符的定义，将这个表转换为二进制文件，并确保这种分隔符模式永远不会在数据本身中使用。例如，如果您选择了 < * > 作为分隔列的例子，那么您应该验证放置在此表中的数据，以避免包含此模式。您还可以通过指定行的大小和一些内部索引编号来使用行标头和列标头来加快搜索速度，并且在每个列的开始处具有该列的长度 比如“亚当”1.11.1“ ABC 街123号邮箱456” 你可以像这样 亚当 < & Col2，Num，1,0 > 1 < & Col3，Num，2,1 > 111 < & Col4，CHER，24 > 123 ABC Street POBox 456 < & RowTrailer >

  • 如何快速找到物品 尝试使用散列和索引来指向根据不同条件存储和缓存的数据 以上面的同一个例子为例，您可以对第一列的值进行排序，并将其存储在一个单独的对象中，该对象指向按字母顺序排序的项的行 id，依此类推，如

  • 如何加速插入数据 我从 Oracle 得知，他们将数据插入到 RAM 和磁盘中的一个临时位置，并定期进行内务管理，数据库引擎一直忙于优化其结构，但同时我们也不希望在类似的断电情况下丢失数据。 因此，尝试将数据保存在这个没有排序的临时位置，添加您的原始存储，并在以后当系统是自由的时候使用您的索引，并在完成

    • 时清除临时区域

祝你好运，伟大的项目。

小开

我不确定它是否适合您的需求，但是我已经实现了一个简单的面向文件的数据库，并且使用 perl 支持 simple (SELECT, INSERT , UPDATE)。
我所做的是将每个表作为一个文件存储在磁盘上，并使用定义良好的模式对条目进行存储，并在构建的 Linux 工具(如 awk 和 sed)中使用数据进行操作。为了提高效率，经常访问的数据被缓存。

小开

如果您对 MySQL 感兴趣，我还建议使用这个 维基页面，它有一些关于 MySQL 如何工作的信息。此外，您可能想看看 了解 MySQL 内部结构。

您还可以考虑为数据库引擎查看非 SQL 接口。请看 Apache CouchDB。这就是所谓的面向文档的数据库系统。

祝你好运！

小开

前面提到过 SQLite，但是我想添加一些东西。

我个人通过学习 SQlite 学到了很多。有趣的是，我没有查看源代码(尽管我只是简单地看了一下)。通过阅读技术材料，特别是研究它产生的内部命令，我学到了很多。它内部有一个自己的基于堆栈的解释器，你可以通过解释来读取它内部生成的 P 代码。因此，您可以看到各种构造是如何转换为低级引擎的(这非常简单——但这也是其稳定性和效率的秘密)。

小开

好的，我已经找到一个网站，其中有一些关于 SQL 和实现的信息-这是一个有点难以链接到网页列出所有的教程，所以我将链接他们一个一个:


提交答案