我知道B树是如何在内存中工作的,它很容易实现。然而,目前我完全无法理解的是,如何找到在磁盘上有效工作的数据布局,这样:
如果有人能提供关于在磁盘级别上布局B树结构的见解,我将非常感激。尤其是最后一点让我头疼。我也会喜欢指向书籍的指针,但我所见过的大多数数据库文献只解释了高级结构(即“这是在内存中这样做的”),但跳过了磁盘布局上的细节。
发布于 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,用于算术简化):
当从一个大索引读取信息时:可以如下:
一个非常大的索引可以在多个文件上拆分,那么块的地址将为(filename_id,address_relative_to_this_file)。
发布于 2016-11-22 11:35:06
https://stackoverflow.com/questions/40740752
复制相似问题