searching in multiway tree searching for an item with key in multiway search tree is simple we perform such search by tracing path in starting at the root (see figure and when we are at -node during this searchwe compare the key with the keys kd- stored at if ki for some ithe search is successfully completed otherwisewe continue the search in the child ci of such that ki- ki (recall that we conventionally define and kd if we reach an external nodethen we know that there is no item with key in and the search terminates unsuccessfully data structures for representing multiway search trees in section we discuss linked data structure for representing general tree this representation can also be used for multiway search tree when using general tree to implement multiway search treewe must store at each node one or more key-value pairs associated with that node that iswe need to store with reference to some collection that stores the items for during search for key in multiway search treethe primary operation needed when navigating node is finding the smallest key at that node that is greater than or equal to for this reasonit is natural to model the information at node itself as sorted mapallowing use of the find ge(kmethod we say such map serves as secondary data structure to support the primary data structure represented by the entire multiway search tree this reasoning may at first seem like circular argumentsince we need representation of (secondaryordered map to represent (primaryordered map we can avoid any circular dependencehoweverby using the bootstrapping techniquewhere we use simple solution to problem to create newmore advanced solution in the context of multiway search treea natural choice for the secondary structure at each node is the sortedtablemap of section because we want to determine the associated value in case of match for key kand otherwise the corresponding child ci such that ki- ki we recommend having each key ki in the secondary structure map to the pair (vi ci with such realization of multiway search tree processing -node while searching for an item of with key can be performed using binary search operation in (log dtime let dmax denote the maximum number of children of any node of and let denote the height of the search time in multiway search tree is therefore ( log dmax if dmax is constantthe running time for performing search is (hthe primary efficiency goal for multiway search tree is to keep the height as small as possible we next discuss strategy that caps dmax at while guaranteeing height that is logarithmic in nthe total number of items stored in the map