如何在磁盘上布局 B-Tree 数据？

Question

我知道 B-Tree 如何在内存中工作，它很容易实现。但是，我不知道如何找到在磁盘上有效工作的数据布局，例如：

• B-Tree 中的条目数可以无限增长（或至少增长到 > 1000GB）
• 磁盘级复制操作最小化
• 值可以有任意大小（即没有固定模式）

如何以符合这些标准的方式在磁盘级别布局 B-Tree 结构？最后一个要点尤其让我很头疼。我见过的大多数数据库文献只解释了高级结构（即“这就是你在内存中的做法”），但跳过了磁盘布局的细节。

Answer 1

https://web.archive.org/web/20161221112438/http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-到内部

备注：

数据库不直接基于 B 树实现索引，而是基于称为 B+ 树的变体。根据维基百科：

B+ 树可以看作是一个 B 树，其中每个节点只包含键（而不是键值对），并且在底部添加了一个附加层，并带有链接的叶子。

数据库通常使用面向块的存储，而 b+ 树比 b 树更适合这种情况。

块是固定大小的，并留有一些可用空间以适应未来值或键大小的变化。

块可以是叶子（保存实际数据）或分支（保存指向叶节点的指针）

如何实现写入磁盘的玩具模型（用于算术简化的块大小 10k）：

1. 在磁盘上创建一个 10G 的文件（它有 1000 个块）
2. 第一个块被分配为根，下一个空闲块被分配为叶，叶地址列表被放入根
3. 新数据插入，当前叶节点填充值直到达到阈值
4. 数据继续插入，下一个空闲的分配为叶块并更新叶节点列表
5. 多次插入后，当前根节点需要子节点，所以下一个空闲块被分配为分支节点，它从根复制列表，现在根将只维护一个中间节点列表。
6. 如果需要拆分节点块，则分配下一个空闲块作为分支节点，添加到根列表中，叶节点列表在初始和新分支节点之间拆分

从大索引中读取信息时：可以去如下：

1. read first/root block (seek(0), read(10k)) 指向位于块 900 中的子节点
2. read block 900 (seek(900*10k), read(10K)) 指向位于 block 5000 中的孩子
3. read block 5000 (seek(5000*10k), read(10K)) 指向位于block 190的叶子节点
4. 读取块 190 (seek(190*10k), read(10K)) 并从中提取感兴趣的值

一个非常大的索引可以在多个文件上拆分，那么块的地址将是 (filename_id, address_relative_to_this_file)