1

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 ?

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

But i dont fully understand the answer.

please share your views ?

Community
  • 1
  • 1
Abhishek Sagar
  • 1,189
  • 4
  • 20
  • 44
  • What is the difference between a memory address and an offset from the start of the time? –  Apr 24 '12 at 05:17

2 Answers2

0

Take a look at the code of JDBM3 in github. This project persists B+ Tree and similar data structures to disk and you will definitely find your answer there.

Abe
  • 8,623
  • 10
  • 50
  • 74
0

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).

dande
  • 233
  • 2
  • 11
  • Can you also provide some high level overview of how traversal of a b tree (index for databases) happens on disk itself and use it to fetch the disk pages? – user104309 Sep 03 '17 at 20:30