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

Question

我知道 B-Tree 如何在内存中工作，它很容易实现。然而，目前我完全无法理解的是如何找到在磁盘上有效工作的数据布局，例如:

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

如果有人能提供有关在磁盘级别布局 B 树结构的见解，我将不胜感激。特别是最后一个要点让我很头疼。我也很感激书籍的指针，但我看到的大多数数据库文献只解释了高级结构(即“这就是你在内存中做的事情”)，但跳过了磁盘布局的细节。

Answer 1

更新(Oracle 索引内部的存档版本):http://web.archive.org/web/20161221112438/http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals

---

OLD(原来的链接不存在了): 关于 Oracle 索引内部结构的一些信息:http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals

注意事项:

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

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key-value pairs), and to which an additional level is added at the bottom with linked leaves.

一般来说，数据库使用面向 block 的存储，而 b+ 树比 b 树更适合这种情况。

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

block 可以是叶(保存实际数据)或分支(保存指向叶节点的指针)

如何实现写入磁盘的玩具模型(用于算术简化的 block 大小 10k):

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

当从一个大索引中读取信息时:可以去如下:

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

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