磁盘数据结构的架构

alf*_*alf 5 c database filesystems b-tree disk

我最接近最终理解磁盘 btree 架构的是这个.

它很简单,很容易阅读和理解。但是我还是觉得很迷茫。似乎根本没有内存数据结构。我错过了什么吗?是什么让这成为一个 btree?是否只是“指向”其子节点键的 long 数组?这样有效率吗?大多数数据库和文件系统就是这样设计的吗?

是否有在内存中的磁盘 btree(或其他数据结构)上实现的方法?每个节点在哪里包含文件偏移量之类的?

Mår*_*röm 2

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

一般来说,实现选择使用物理地址或逻辑地址:

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

物理寻址速度更快(因为不需要解析机制)。然而,逻辑寻址可以允许重组节点而不必重写指针。能够以这种方式重新组织节点的能力可以作为实现良好的集群、空间利用甚至低级数据分布的基础。

一些实现使用逻辑和物理寻址的组合,使得每个地址由(动态地)引用段(blob)的逻辑地址和该段内的物理地址组成。

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

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

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

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