磁盘数据库如何处理文件系统级别的文件读取和写入？

Question

假设我用c ++编写自己的数据库，并假设我会使用二叉树或哈希映射作为底层数据结构。我该如何处理这个数据结构的更新？

1）我应该首先创建二叉树，然后以某种方式将其持久保存到磁盘上吗？每次数据都需要更新时，我需要打开这个文件并进行更新吗？这不是一项昂贵的操作吗？

2）有没有办法直接处理二叉树而不将其加载到内存中然后再次持久化？

3）SQLite和Mysql如何处理它？

4）我的主要问题是，数据库如何保存大量数据并同时对其进行更新，而无需每次都打开和关闭文件。

Answer 1

数据库将磁盘或文件视为一个大块设备并管理M-way Balanced Trees中的块。它们在这些块中插入/更新/删除记录，并再次将脏块刷新到磁盘。它们管理空闲块的分配表，因此不需要在每次访问时重写数据库。由于RAM内存昂贵但速度很快，因此页面保存在RAM缓存中。单独的索引（单独的文件或只是块）管理基于密钥的快速访问。块通常是底层文件系统的本机分配大小（例如，簇大小）。撤销/重做日志的原子性保持不变。等等

还有更多要说的，这个问题实际上属于计算机科学堆栈交换。有关更多信息，请阅读Horowitz＆Sahni，“数据结构基础”，第496页。

至于你的问题：

1. 您打开它一次并在数据库管理器运行时保持打开状态。您可以根据需要分配存储并维护M路树，如上所述。
2. 是。您读取保存在缓存中的块。
3. 和4：见上文。

Answer 2

通常，您不会执行文件I / O来访问数据。使用mmap将数据映射到进程的虚拟地址空间，并让OS块缓存处理读写操作。