database - 在单个文件中实现数据库

Question

这个问题是关于创建一个新的单文件数据库格式。我是新来的！

我想知道 SQLite 是如何做到这一点的——对于大于可用内存的数据库，SQLite 必须以某种方式从文件的某些部分读取，即在位置 n 处读取？

这在亚线性运行时复杂度下是否可能？我假设当 SQLite 获取特定行时，它首先使用 O(logn) 索引查找 - 所以它不会获取整个索引 - 然后它从文件中的特定位置获取行。所有这些都涉及不将整个文件读入内存——但 FS 方法似乎不提供此功能。

fs.skip(n) [伪代码] 是在 O(n) 中完成还是操作系统直接跳到位置 n？从理论上讲，这应该是可能的，因为在 OS 文件中，文件被分为块 - 并且 inode 引用 1-3 级的类似数组的结构来定位块，因此在亚线性时间内获取文件中的特定块应该是可能的 - 无需读取整个文件。

标签： databasefsflat-fileinode

Answer 1

我想知道 SQLite 是如何做到这一点的——对于大于可用内存的数据库，SQLite 必须以某种方式从文件的某些部分读取，即在位置 n 处读取？

是的。几乎每种编程语言都有解释如何在文件上定位读取的文档。

所有这些都涉及不将整个文件读入内存——但 FS 方法似乎不提供此功能。

我知道的每个文件系统访问 API都支持这一点，文档中对此进行了解释。示例范围从 Windows 中的内存映射文件（如果您计划与操作系统无关，则“相当”高级且不支持），到诸如fseek()C 中定位文件流的方法这样简单的东西。

我建议用你选择的编程语言复习你对文件系统访问方法的了解。