Search


Software Design Using C++



B-Tree Retrieve Function



Example


Let's go through an example of how the Retrieve function works when looking up a particular search key in a B-tree. Refer back to the B-Tree Example to see the complete code and an overview of the code. In tracing the operation of the Retrieve function we will also have to look at the SearchNode function.

Suppose that we use the Retrieve function to look for SearchKey GB. We will trace the operation of the Retrieve function in the picture below. (A larger picture is available if you wish to use it.) Let's assume that record (node) 2 is the root node. Special record 0 is not shown in the picture to save space. We also draw a B-tree of order 5 to save space, even though the B-Tree Example is coded for a B-tree of order 12. In the drawing note that the number at the bottom of each array location is the index number.

[B-tree retrieval picture]

As seen in btree.cpp, CurrentRoot begins at the root value, 2 in this case. Found starts at false. Record 2 of the file is thus read into CurrentNode. The SearchNode function is then used to look for GB in CurrentNode. SearchNode does a sequential search starting at the last key in the node and moving left. When it reaches the G, it realizes that GB is not in this node. SearchNode returns false and sends back index 1 in parameter Location. Retrieve then puts Branch[Location + 1] = Branch[2] = 1 into CurrentRoot in order to follow Branch[2] to node 1.

The next time through the loop, record 1 is read into CurrentNode. SearchNode does its sequential search for GB. It stops at GA and returns false to say that GB was not found. Location = 0 is sent back as well. Retrieve then puts Branch[Location + 1] = Branch[1] = 3 into CurrentRoot in order to follow Branch[1] to node 3.

The next time through the loop, record 3 is read into CurrentNode. SearchNode does its sequential search for GB. It stops at GB and returns true to say that GB was found. Location = 2 is sent back also. Retrieve then copies the Key[2] structure containing GB and its associated DataField into parameter Item and then returns true since GB was found.

Back to the main page for Software Design Using C++

Authors: Br. David Carlson and Br. Isidore Minerd
Last updated: August 27, 2009