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

Question

我知道B-Tree如何在内存中工作,它很容易实现.但是,目前完全超出我的是如何找到在磁盘上有效工作的数据布局,例如:

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

如果有人能够深入了解磁盘级布局B树结构,我将非常感激.特别是最后一个要点让我头疼不已.我也很欣赏指向书籍,但我见过的大多数数据库文献只解释了高级结构(即"这就是你在内存中的表现"),但是跳过了磁盘布局上的细节.

Answer 1

有关oracle index internals的一些信息:http: //www.toadworld.com/platforms/oracle/w/wiki/11001.oracle-b-tree-index-from-the-concept-to-internals

笔记:

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

B +树可以被视为B树,其中每个节点仅包含键(不是键值对),并且在底部添加了附加级别的链接叶.

通常,数据库使用面向块的存储,而b +树更适合用于此的b树.

这些块是固定大小的,并留有一些空闲空间,以适应未来价值或密钥大小的变化.

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

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

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

从大索引中读取信息时:可以执行以下操作:

1. 读取第一个/根块(seek(0),read(10k)),其指向位于块900中的子节点
2. 读取块900(寻找(900*10k),读取(10K)),其指向位于块5000中的孩子
3. 读取块5000(搜索(5000*10k),读取(10K)),其指向位于块190中的叶节点
4. 读取块190(搜索(190*10k),读取(10K))并从中提取感兴趣的值

一个非常大的索引可以拆分多个文件,然后块的地址将是(filename_id,address_relative_to_this_file)