我知道 B-Tree 如何在内存中工作，它很容易实现。但是，目前完全超出了我的范围，是如何找到在磁盘上有效工作的数据布局，例如：
- B-Tree 中的条目数可以无限增长（或至少超过 1000GB）
- 磁盘级复制操作被最小化
- 这些值可以有任意大小（即没有固定模式）
如果有人可以提供有关在磁盘级别布局 B-Tree 结构的见解，我将不胜感激。尤其是最后一个要点让我很头疼。我也很欣赏书籍的指针，但我见过的大多数数据库文献只解释了高级结构（即“这就是你在内存中的做法”），但跳过了磁盘布局的细节。
问问题
8766 次
2 回答
28
更新（oracle 索引内部的存档版本）：http ://web.archive.org/web/20161221112438/http://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-从概念到内部的索引
旧（原始链接不再存在）：有关 oracle 索引内部的一些信息： http ://www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-概念到内部
笔记：
数据库不直接实现基于 B-tree 的索引，而是基于称为 B+ 树的变体。根据维基百科：
B+树可以看作是一个B树，其中每个节点只包含键（不是键值对），并且在底部添加了一个额外的级别，带有链接的叶子。
一般来说，数据库使用面向块的存储，b+ 树比 b-tree 更适合于此。
这些块是固定大小的，并留有一些可用空间以适应未来值或密钥大小的变化。
块可以是叶子（保存实际数据）或分支（保存指向叶子节点的指针）
一个如何实现写入磁盘的玩具模型（用于算术简化的块大小为 10k）：
- 在磁盘上创建一个 10G 的文件（它有 1000 个块）
- 第一个块被分配为根，下一个空闲块作为叶子，叶子地址列表被放入根
- 插入新数据，当前叶节点填充值直到达到阈值
- 继续插入数据，下一个空闲的被分配为叶块，叶节点列表被更新
- 在多次插入之后，当前根节点需要子节点，因此下一个空闲块被分配为分支节点，它从根节点复制列表，现在根节点将只维护一个中间节点列表。
- 如果需要拆分节点块，则分配下一个空闲块作为分支节点，添加到根列表中，叶节点列表在初始分支节点和新分支节点之间进行拆分
当从大索引中读取信息时：可以如下：
- 读取第一个/根块 (seek(0), read(10k))，它指向位于块 900 中的子节点
- 读取块 900 (seek(900*10k), read(10K))，它指向位于块 5000 中的子节点
- 读取块 5000 (seek(5000*10k), read(10K))，它指向位于块 190 中的叶节点
- 读取块 190 (seek(190*10k), read(10K)) 并从中提取感兴趣的值
一个非常大的索引可以在多个文件上拆分，那么块的地址将是 (filename_id, address_relative_to_this_file)
于 2016-11-22T11:38:47.703 回答
-2
于 2016-11-22T11:35:06.423 回答