首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何在磁盘上放置B树数据?

问如何在磁盘上放置B树数据?
EN

Stack Overflow用户
提问于 2016-11-22 11:32:42
回答 2查看 10.3K关注 0票数 29

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

  • B树中的条目数可能会不确定地增长(或至少增长到>1000 to )。
  • 磁盘级复制操作被最小化。
  • 这些值可以具有任意大小(即没有固定模式)。

如果有人能提供关于在磁盘级别上布局B树结构的见解,我将非常感激。尤其是最后一点让我头疼。我也会喜欢指向书籍的指针,但我所见过的大多数数据库文献只解释了高级结构(即“这是在内存中这样做的”),但跳过了磁盘布局上的细节。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2016-11-22 11:38:47

更新( 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

旧的(原来的链接已经不存在了):关于oracle索引内部的一些信息: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. 第一个块被赋值为根,下一个块被赋值为叶,并将一个叶地址列表放在根中。
  3. 插入新数据时,当前叶节点将填充值,直到达到阈值为止。
  4. 数据继续插入,下一个空闲数据作为叶块分配,叶节点列表被更新为。
    1. 在多次插入之后,当前根节点需要子节点,因此下一个空闲块被分配为分支节点,它从根节点复制列表,现在根将只维护一个中间节点列表。
    2. 如果需要拆分节点块,则将下一个空闲块分配为分支节点,将其添加到根列表中,并将叶节点列表拆分为初始分支节点和新分支节点。

​

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

  1. 读取第一个/根块(查找(0),读(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)。

票数 30
EN

Stack Overflow用户

发布于 2016-11-22 11:35:06

票数 -2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/40740752

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档