如何在磁盘上布局 B-Tree 数据？
How to lay out B-Tree data on disk?
我知道 B-Tree 在内存中是如何工作的，它很容易实现。然而，目前我完全无法理解的是如何找到在磁盘上有效工作的数据布局，例如：
- B 树中的条目数可以无限增长（或至少增长到 > 1000GB）
- 磁盘级复制操作被最小化
- 值可以有任意大小（即没有固定模式）
如果有人能提供有关在磁盘级别布局 B 树结构的见解，我将不胜感激。特别是最后一个要点让我很头疼。我也很感激书籍的指针，但我看到的大多数数据库文献只解释了高级结构（即 "this is how you do it in memory"），但跳过了磁盘布局的细节。
阅读
这绝对有帮助
http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/
更新（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（原来的link已经不存在了）：
关于 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.
数据库通常使用面向块的存储，而 b+ 树比 b 树更适合这种情况。
这些块是固定大小的，并留有一些空闲 space 以适应未来值或键大小的变化。
块可以是叶（保存实际数据）或分支（保存指向叶节点的指针）
如何实现写入磁盘的玩具模型（用于算术简化的块大小 10k）：
- 在磁盘上创建了一个 10G 的文件（它有 1000 个块）
- 第一个块被分配为根，下一个空闲块被分配为叶，叶地址列表被放入根
- 插入新数据，当前叶节点填充值，直到达到阈值
- 数据继续插入，下一个空闲的分配为叶块并更新叶节点列表
- 经过多次插入后，当前根节点需要子节点，所以下一个空闲块被分配为分支节点，它从根复制列表，现在根将只维护一个中间节点列表。
- 如果需要拆分节点块，则分配下一个空闲块作为分支节点，添加到根列表中，叶节点列表在初始和新分支节点之间拆分
从大索引中读取信息时：可以走以下：
- read first/root block (seek(0), read(10k)) 指向位于 block 900
的子节点
- 读取块 900 (seek(900*10k), read(10K)) 指向位于块 5000 中的子节点
- read block 5000 (seek(5000*10k), read(10K)) 指向位于block 190的叶子节点
- 读取块190（查找（190*10k），读取（10K））并从中提取感兴趣的值
一个非常大的索引可以在多个文件上拆分，那么块的地址将是 (filename_id, address_relative_to_this_file)
我知道 B-Tree 在内存中是如何工作的，它很容易实现。然而，目前我完全无法理解的是如何找到在磁盘上有效工作的数据布局，例如：
- B 树中的条目数可以无限增长（或至少增长到 > 1000GB）
- 磁盘级复制操作被最小化
- 值可以有任意大小（即没有固定模式）
如果有人能提供有关在磁盘级别布局 B 树结构的见解，我将不胜感激。特别是最后一个要点让我很头疼。我也很感激书籍的指针，但我看到的大多数数据库文献只解释了高级结构（即 "this is how you do it in memory"），但跳过了磁盘布局的细节。
阅读 这绝对有帮助 http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/
更新（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（原来的link已经不存在了）： 关于 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.
数据库通常使用面向块的存储，而 b+ 树比 b 树更适合这种情况。
这些块是固定大小的，并留有一些空闲 space 以适应未来值或键大小的变化。
块可以是叶（保存实际数据）或分支（保存指向叶节点的指针）
如何实现写入磁盘的玩具模型（用于算术简化的块大小 10k）：
- 在磁盘上创建了一个 10G 的文件（它有 1000 个块）
- 第一个块被分配为根，下一个空闲块被分配为叶，叶地址列表被放入根
- 插入新数据，当前叶节点填充值，直到达到阈值
- 数据继续插入，下一个空闲的分配为叶块并更新叶节点列表
- 经过多次插入后，当前根节点需要子节点，所以下一个空闲块被分配为分支节点，它从根复制列表，现在根将只维护一个中间节点列表。
- 如果需要拆分节点块，则分配下一个空闲块作为分支节点，添加到根列表中，叶节点列表在初始和新分支节点之间拆分
从大索引中读取信息时：可以走以下：
- read first/root block (seek(0), read(10k)) 指向位于 block 900 的子节点
- 读取块 900 (seek(900*10k), read(10K)) 指向位于块 5000 中的子节点
- read block 5000 (seek(5000*10k), read(10K)) 指向位于block 190的叶子节点
- 读取块190（查找（190*10k），读取（10K））并从中提取感兴趣的值
一个非常大的索引可以在多个文件上拆分，那么块的地址将是 (filename_id, address_relative_to_this_file)