chap indexing figure -tree of order four -trees guarantee that every node in the tree will be full at least to certain minimum percentage this improves space efficiency while reducing the typical number of disk fetches necessary during search or update operation -tree of order is defined to have the following shape propertiesthe root is either leaf or has at least two children each internal nodeexcept for the roothas between dm/ and children all leaves are at the same level in the treeso the tree is always height balanced the -tree is generalization of the - tree put another waya - tree is -tree of order three normallythe size of node in the -tree is chosen to fill disk block -tree node implementation typically allows or more children thusa -tree node is equivalent to disk blockand "pointervalue stored in the tree is actually the number of the block containing the child node (usually interpreted as an offset from the beginning of the corresponding disk filein typical applicationb-tree block / will be managed using buffer pool and block-replacement scheme such as lru (see section figure shows -tree of order four each node contains up to three keysand internal nodes have up to four children search in -tree is generalization of search in - tree it is an alternating two-step processbeginning with the root node of the -tree perform binary search on the records in the current node if record with the search key is foundthen return that record if the current node is leaf node and the key is not foundthen report an unsuccessful search otherwisefollow the proper branch and repeat the process for exampleconsider search for the record with key value in the tree of figure the root node is examined and the second (rightbranch taken after