chap indexing valuesbut these are used solely as placeholders to guide the search this means that internal nodes are significantly different in structure from leaf nodes internal nodes store keys to guide the searchassociating each key with pointer to child -tree node leaf nodes store actual recordsor else keys and pointers to actual records in separate disk file if the -tree is being used purely as an index depending on the size of record as compared to the size of keya leaf node in -tree of order might have enough room to store more or less than records the requirement is simply that the leaf nodes store enough records to remain at least half full the leaf nodes of -tree are normally linked together to form doubly linked list thusthe entire collection of records can be traversed in sorted order by visiting all the leaf nodes on the linked list here is java-like pseudocode representation for the -tree node interface leaf node and internal node subclasses would implement this interface /*interface for btree nodes *public interface bpnode public boolean isleaf()public int numrecs()public key[keys()an important implementation detail to note is that while figure shows internal nodes containing three keys and four pointersclass bpnode is slightly different in that it stores key/pointer pairs figure shows the -tree as it is traditionally drawn to simplify implementation in practicenodes really do associate key with each pointer each internal node should be assumed to hold in the leftmost position an additional key that is less than or equal to any possible key value in the node' leftmost subtree -tree implementations typically store an additional dummy record in the leftmost leaf node whose key value is less than any legal key value -trees are exceptionally good for range queries once the first record in the range has been foundthe rest of the records with keys in the range can be accessed by sequential processing of the remaining records in the first nodeand then continuing down the linked list of leaf nodes as far as necessary figure illustrates the -tree search in -tree is nearly identical to search in regular -treeexcept that the search must always continue to the proper leaf node even if the search-key value is found in an internal nodethis is only placeholder and does not provide access to the actual record to find record with key value in the -tree of figure search begins at the root the value stored in the root merely serves as placeholderindicating that keys with values greater than or equal to