How to implement a file-based binary search tree structure

[schauerlich]

Ah. I'm confusing them with another tree then that outperformed rb, but mostly in unimportant limit situations. Thanks for clarifying.

B-trees aren't binary search trees. The try to be wider than they are deep in order to minimize the average depth of a piece of data. Since each level you go down is another potential disk access, keeping the tree as flat as possible will greatly speed things up. If one disk access costs the same amount of time as dereferencing 1000 pointers and comparing memory contents, you'd rather have a tree of depth ~10 and process 100 things in memory per node than do 1000 disk accesses with only one comparison each.

[wirate]

Red-black trees look like a good idea. However, AVL and B-trees are way too complex for me and their advantages are not very much required. I am not looking for heavy disk I/O optimization. Completing the project is a big enough challenge here.

Let me be a little more descriptive now. In my search engine project, I will have a list of keywords and their IDs, a list of webpages and their IDs and a tree relating each keyword to a number of pages.

Each node is supposed to be representing a keyword and contain a pointer to a list of webpages that are relevant for that keyword along with their relevance scores. So when the user enters a query in the search engine, the program looks for that keyword in the tree and displays the list of related webpages in decreasing order of their relevance scores. Fairly simple.

Now the problem is that all these lists have to reside on disk and they have to be read in at the time of executing the query. You can see from the above description that I am a newbie Please help me out

[schauerlich]

Red-Black trees are more complex to implement than AVL trees, IMO. Once you learn the rotations, AVL is pretty simple. Red-Black, not so much.