c - 磁盘数据结构的架构

Question

最接近我最终了解磁盘 btree 架构的是this。

它很简单，很容易阅读和理解。但我仍然感到困惑。似乎根本没有任何内存数据结构。我错过了什么吗？是什么使它成为 btree？仅仅是“指向”其子节点键的 long 数组吗？那效率高吗？这就是大多数数据库和文件系统的设计方式吗？

有没有办法在内存中的磁盘 btree（或其他数据结构）上实现？每个节点在哪里包含一个文件偏移量或什么？

Answer 1

节点指针通常作为地址存储在磁盘上（例如使用长整数）。

通常，实现选择使用物理地址或逻辑地址：

• 物理地址指定存储节点的实际偏移量（在文件或类似文件中）。
• 相反，逻辑地址需要某种机制，每次导航/遍历指针时解析为物理地址。

物理寻址更快（因为不需要解析机制）。但是，逻辑寻址可以允许重新组织节点而无需重写指针。能够以这种方式重新组织节点的能力可以作为实现良好聚类、空间利用率甚至低级数据分布的基础。

一些实现使用逻辑和物理寻址的组合，使得每个地址都由一个（动态地）指向段（blob）的逻辑地址和该段内的物理地址组成。

重要的是要注意节点地址是基于磁盘的，因此它们不能直接转换为内存中的指针。

在某些情况下，当数据加载到内存时将基于磁盘的指针转换为内存指针（然后在写入时转换回基于磁盘的指针）是有益的。

这种转换有时称为指针混合，可以通过多种方式实现。基本思想是，在指针被导航/遍历之前，不应将由混杂的内存指针寻址的数据加载到内存中。

常见的方法是使用逻辑内存寻址方案或使用内存映射文件。内存映射文件使用虚拟内存寻址，其中内存页面在访问之前不会加载到内存中。虚拟内存映射文件由操作系统提供。这种方法有时称为缺页寻址，因为访问尚未映射到内存的内存页面上的数据会导致缺页中断。