Implementing Tree Structure in disk memory

Question

I am writing some data to a text file(stored in disk) as output from my program. I want to organize the data in the text file in a search tree format so that it facilitates efficient search and replace(through the program itself). I would like to know how to implement the tree structure to be stored in a disk memory.

Answer 1

One of the main practical difficulties of using a tree data-structure on disk is that with naive binary trees data will be "far apart" and trying to access this data will likely cause thrashing as your hard drive attempts to continuously access different locations on disk.

The classic solution to this problem is to use B-trees. The basic idea behind B-trees is that reads from disk are expensive so you should use them as little as possible. This is accomplished by using large nodes; instead of storing only two children, B-trees can have m children. This greatly increases the entropy of each node meaning that it takes far fewer reads to access you data.

Some more reading on B-trees can be found here, the pictures are particularly helpful in my opinion, and several implementations on B-trees can be found here.