维护“链接"将B +树写入磁盘时? [英] Maintain "links" when writing a B+ tree to disk?

问题描述

我已经在Java中实现了B +树的实现，但是像往常一样，它完全在主内存中.如何将B +树存储到磁盘上?btree的每个节点都包含指向其子节点的指针(主内存地址或对对象的引用)，当Btree驻留在磁盘上时，我如何实现类似的目的?在b +树在磁盘上的情况下，什么替换b +树节点中的主内存地址?

I have done the implementation of B+ tree in java , but as usual , that is completely in main memory. How can i store a B+ tree onto a disk ? Each node of the btree contains the pointers(main memory addresses or reference to objects) to its children , how can i achieve the similar thing while Btree resides on disk? What replaces main memory addresses in b+ tree nodes in the scenario when b+ tree is on disk ?

这里已经发布了类似的问题: Java中的B + Tree磁盘实现

There is already a similar Question posted here : B+Tree on-disk implementation in Java

但是我不完全理解答案.

But i dont fully understand the answer.

请分享您的看法?

推荐答案

以最简单的形式:您必须跟踪当前当前的文件偏移量(距文件开头的字节数).节点被读取或写入.因此，您可以在基于文件的DB上而不是内存地址中保存偏移量.

In the most simplistic form: You will have to keep track of the file offset (the number of bytes from the start of the file) the current node is read from or written to. So instead of memory addresses, on file based DBs, you save offsets.

然后，当从文件中读取文件时，您可以决定将其缓存"在内存中，并保存给定节点的内存地址，或者仅对偏移量进行操作.

Then when it is read from the file, you can decide to "cache" it in memory, and save the memory address for the given node, or only operate on offsets.

这样说，我必须补充一点，通常基于文件的数据库要比这复杂得多，通过将节点写入页面(通常与磁盘上的页面大小相同)来优化磁盘访问.这样，您可以通过一次磁盘查找操作(被认为是昂贵的操作)读取多个节点.

With this said, I have to add, that usually a file based DB is more complicated than this, optimising disk access by writing nodes to pages (which are usually the same size as the pages on the disk). This way, you can read more than one node with one disk seek operation (regarded as expensive operation).

这篇关于维护“链接"将B +树写入磁盘时?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！