notes height of -trees for greater than or equal to onethe height of an -key -tree of height with minimum degree greater than or equal to <log + the worst case height is (log nsince the "branchinessof -tree can be large compared to many other balanced tree structuresthe base of the logarithm tends to be largethereforethe number of nodes visited during search tends to be smaller than required by other tree structures although this does not affect the asymptotic worst case heightb-trees tend to have smaller heights than other trees with the same asymptotic height operations on -trees the algorithms for the searchcreateand insert operations are shown below note that these algorithms are single passin other wordsthey do not traverse back up the tree since -trees strive to minimize disk accesses and the nodes are usually stored on diskthis single-pass approach will reduce the number of node visits and thus the number of disk accesses simpler double-pass approaches that move back up the tree to fix violations are possible since all nodes are assumed to be stored in secondary storage (diskrather than primary storage (memory)all references to given node be be preceeded by read operation denoted by diskread similarlyonce node is modified and it is no longer neededit must be written out to secondary storage with write operation denoted by disk-write the algorithms below assume that all nodes referenced in parameters have already had corresponding disk-read operation new nodes are created and assigned storage with the allocate-node call the implementation details of the disk-readdisk-writeand allocate-node functions are operating system and implementation dependent -tree-search(xki < while keyi[xdo < if < [xand keyi[xthen return (xiif leaf[xthen return nil else disk-read(ci[ ]return -tree-search(ci[ ]kthe search operation on -tree is analogous to search on binary tree instead of choosing between left and right child as in binary treea -tree search must make an -way choice the correct child is chosen by performing linear search of the values in the node after finding the value greater than or equal to the desired valuethe child pointer to the immediate left of that value is followed if all values are less than the desired valuethe rightmost child pointer is followed of coursethe search can be terminated as soon as the desired node is found since the running time of the search operation depends upon the height of the treeb-tree-search is (logt nb-tree-create(tx <allocate-node( lovely professional university