To simplify the introduction of B-trees, no strict algorithms and formalism are given. Instead informal discussions will be given to illustrate B-trees.
To show the search algorithm of B-trees, three search scenarios are given as follows:
Key Appearing in the Interior Nodes
To search for the data record whose key value is P, we search the node at the first level and find that the first key is P. We use its reference value (arrow) to access the first node of the second level and search that node. We find P as the third key of this node and use its reference to access the third node of the third level. We find P as the second key.
Key Not Appearing in the Interior Nodes
To search for the key value G, we search the node at the first level and do not find G in the root node. Because G is less than or equal to P, we should look for G in the second-level node pointed to by P. Looking in the first node in the second level, we again do not find G, but conclude that we should look in the third-level node pointed to by key M. In this node, we find G, extract the data record address, and read the data file.
Key Not Appearing in the Tree
A search for F, which does not appear in the tree, follows the same path as the search for G. When we get to the bottom of the tree, we do not find F and must conclude that no data record with key F exists.
