Arrangement for enhancing weighted element searches in dynamically balanced trees

[0002] 1. Field of the Invention

[0003] The present invention relates to computer-implemented search techniques, more specifically to arrangements for improving search methodologies in dynamically balanced trees.

[0004] 2. Description of the Related Art

[0005] Different computer-based search techniques have been developed in an effort to reduce the time necessary to search for data records within a computerized database. Examples of conventional search techniques include sequential searches of database records in an ordered table, or binary searches of database records based on a key entry that uniquely identifies a database record.

[0006] These different computer-based search techniques often use a prescribed index to search for a database record. For example, database records may be indexed according to a tree arrangement to quickly insert and locate data. One limitation of trees is that searching of the tree is optimized on the composition of the “key” used to identify tree elements. For example the actual data, or an abstraction or subset of the data is used to uniquely identify each element within the tree. Although trees can be built dynamically as a new data entry is added, a disadvantage of trees is that efficiency of a search operation (i.e., minimizing the average number of data records that need to be accessed during a search) is substantially degraded if the data is not evenly distributed within a tree. A reduced efficiency of a search operation can be critical to performance in time-sensitive applications, such as networked switching systems that need to access network address forwarding information in real time.

[0007] One aspect of even distribution of data involves whether the tree is balanced structurally. FIGS. 1A and 1B are diagrams illustrating a tree having a balanced structure and a tree having an unbalanced structure, respectively. The balanced tree 10, illustrated as a binary tree, has a group of elements 12 that are evenly distributed throughout the tree 10, enabling searches throughout the tree 10 to be performed efficiently relative to the total number of elements 12; in other words, a search through the tree 10 would require at most 4 accesses, based on the depth of the tree 10, where the number of accesses per searche equals log(n), n being equal to the number of elements 12. FIG. 1B is an example of a tree 14 having an unbalanced structure, resulting in possibly a substantial greater number of accesses per search throughout the tree 14. On average, a relatively larger number of access attempts per search are required to find any given element 12 in the unbalanced tree 14.

[0008] A possibly more important aspect of even distribution in a tree involves the distribution of data elements within the tree relative to the frequency in which the data elements are accessed. In particular, the use of trees for searching for a data element provides a reasonable level of efficiency when the data elements in the database have an equal probability of being accessed by a search process. Although this assumption may be true for randomly-distributed groups of data entries such as entries for telephone directories and the like, this assumption is not true for relatively ordered groups of data entries. Use of trees for searching of relatively ordered data entries, or data systems having only a very few heavily-accessed data elements, may cause the tree-type index to have a lumpy distribution.

[0009] For example, the problem of lumpy distribution is substantial in network switches and/or network routers that rely on computer addresses in directing traffic through a network. The problems associated with lumpy distribution may be especially acute if heavily trafficked network nodes, for example servers or gateways, are located deep within the tree 14 (e.g., elements 12band 12c), whereas network nodes having little traffic are located at or near the root of the tree (e.g., element 12a).

[0010] Tree rotation techniques are known for reconfiguring the unbalanced tree 14 into a more balanced structure similar to the balanced tree 10 of FIG. 1A. Although such techniques can balance the structure of the tree, the rotation techniques cannot account for the relative amount of traffic for particular nodes of the tree. Thus, the rotation techniques will result in a structurally balanced tree that still contains a lumpy distribution of data elements; hence, search operation efficiency is still degraded due to the large number of searches needed to locate a heavily accessed element, for example a server or gateway, that is located deep within the tree. If a highly sought after element is positioned at the bottom of a balanced tree, resulting in a lumpy distribution, then the average number of searches will trend towards the depth of the tree, reducing the efficiency of the search operation during use of the balanced tree.

[0011] There is a need for reducing the adverse effects of trees having an lumpy distribution of elements when searching for a given key entry, without sacrificing a search operation for finding or verifying the existence of a key, without the necessity of constant maintenance of the tree.

[0012] There is also a need for an arrangement that enables the bypassing of a tree for identification of the most heavily accessed elements with the minimum number of search operations, regardless of the location of the most heavily accessed elements within the tree.

[0013] These and other needs are attained by the present invention, where additional pointers for each data element are generated that enable the data elements to be searched as a linked list in an order based on determined importance values of the elements within the tree. The searching of the data elements indexed according to a linked list, as opposed to the existing tree structure, enables the search engine of a computer-based system to identify heavily-trafficked elements of the tree with a minimal number of searches.

[0014] According to one aspect of the present invention, a method is provided in a computer system of searching for a specified key entry. The method includes determining an importance value for each element of a tree structure used for searching for the specified key entry. Each of the elements has a corresponding key entry, and the importance value indicates a first probability that the corresponding element includes the specified entry. The method also includes linking at least a first number of the elements according to an order based on the respective determined importance values, determining an estimated average number of accessed elements per search of at least one of the linked first elements and the tree structure, and searching selected linked first elements for the specified key entry, prior to searching the tree structure. The searching of the selected linked first elements of the tree structure is based on the respective importance values being greater than the estimated average number of accessed elements per search. The linking of the first number of the elements according to an order based on the respective determined importance value enables a search engine to identify the most heavily-searched elements of the tree with a minimum number of searches, based on the determined importance values for each of the linked first elements. In addition, the determination of an estimated average number of accessed elements per search enables the linked first elements to identify a point at which a search process should discontinue searching through the linked first elements and begin searching of the tree structure for the specified key entry.

[0015] Hence, the searching for the most heavily-accessed elements can be optimized, without substantially increasing the number of accesses necessary per search for finding an element in the tree structure.

[0016] Additional advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.

[0017] Reference is made to the attached drawings, where elements having the same reference numeral designations represent like elements and wherein:

[0018] FIGS. 1A and 1B are diagrams illustrating balanced and unbalanced trees, respectively.

[0019] FIG. 2 is a block diagram illustrating a processor-based system for searching for a specified key entry according to an embodiment of the present invention.

[0020] FIGS. 3A and 3B illustrate in further detail the indexing of the data elements of FIG. 2 and the data element structure having tree pointers and linked list pointers according to an embodiment of the present invention.

[0021] FIG. 4 summarizes the background process of FIG. 2 for generating the pointers for the doubly linked list according to an embodiment of the present invention.

[0022] FIG. 5 is a flow diagram illustrating the search process of FIG. 2.

[0023] FIGS. 6A and 6B are diagrams illustrating a tree element insertion and removal process of FIG. 2, respectively.

[0024] FIG. 2 is a block diagram illustrating a processor-based system for searching for a specified key entry according to an embodiment of the present invention. The processor-based system 20 includes a search process 22, a background process 24, an element insertion and removal process 26, and a tree element rotation process 28. Each of the processes 22, 24, 26 and 28 may be implemented as executable code stored on a tangible medium, for example a randomly accessible computer memory, disk type memories, digital tapes, and the like, and which is executable by a microprocessor or other CPU within the processor-based system 20. Execution of the instructions stored in the tangible medium by the microprocessor causes certain operations and functions to be performed, described below.

[0025] As described in detail below, the processor-based system 20 is configured for generating and storing a data structure arrangement 30. The data structure arrangement 30 is typically stored in a random access memory internal to the processor-based system 20. The data structure arrangement 30 includes a database 31 that stores a plurality of data elements 34. As described below, the data elements 34 include different pointers that enable the group of data elements to be viewed (i.e., searched) either as a tree or a linked list. For illustration sake, the data elements 34 are illustrated as indexed as a tree structure 32, where one data element 34aserves as a root node for the tree structure.

[0026] FIG. 3A is a diagram illustrating in detail the data elements 34 indexed according to the tree structure 32, and according to a doubly linked list sequence 36. In particular, a selected group of the data elements 34 are indexed according to the doubly linked list sequence 36, enabling a search engine 22 to quickly identify heavily-trafficked elements within the tree structure 32. For example, the doubly linked list sequence 36 is formed by the sequential indexing of data elements 34b, 34c, 34d, 34e, 34f, and 34g, described below.

[0027] The data structure arrangement 30 of FIG. 2 also includes a group of global data elements 40 that are used by the background process 24 for generation and maintenance of the doubly linked list sequence 36. The global elements 40 include a root pointer 40afor pointing to the root element 34aof the tree 32, a top pointer 40bfor pointing to the top element 34b(i.e., the first element) of the doubly-linked list sequence 36, and a bottom pointer 40cfor pointing to the bottom element (e.g., 34g) of the doubly-linked list 36. Note that the doubly-linked list 36 of FIG. 3A is illustrated as having only six data elements 34, although the doubly-linked list 36 would index all the data elements 36 of the tree 32.

[0028] The global elements also include an element counter 40dconfigured for counting the number (E) of elements 34 in the database 31, logically connected into both the tree structure 32 and the doubly-linked list 36. The global elements also include a miss counter 40econfigured for counting a number of misses (M) from searches of data elements 36 (e.g., using the doubly-linked list 36 and/or the tree structure 32) while searching for a specified key entry. For example, if the search process 22 searches through the doubly-linked list 36 and the tree structure 32 for a specified key entry corresponding to a MAC address and the specified entry is not present in the tree structure 32, the miss counter 40eis incremented. The global elements 40 also include a decay factor element 40fconfigured for storing a decay factor (D) that is used for decay or aging functions in determining the relative importance of the elements in the doubly-linked list 36. The global elements 40 also include a target value element 40gconfigured for storing an estimated average number of accessed elements per search, of either the linked list 36 or the tree structure 32, as a target value (T). As described below with respect to FIG. 3B, each of the elements 34 includes a go-to-tree flag that is selectively set based on comparison between the number of matches between the corresponding element relative to a prior number of searches, and the estimated average number (T) of accessed elements per search.

[0029] FIG. 3B is a diagram illustrating the structure of each data element 34. As described above, each data element 34 may be indexed as a tree structure 32 and/or a doubly-linked list 36. As shown in FIG. 3B, each data element 34 includes a key entry 42, and a match counter 44 configured for identifying a number of matches (C) between the corresponding element and key entry searches over a prescribed interval. The element 34 also includes a left pointer 46 and a right pointer 48 as tree pointers for establishing a connection to at least one other element of the tree structure 32. If the element 34 is at a bottom of the tree 32, then the pointer values for the left pointer 46 and the right pointer 48 will have stored null values.

[0030] The data element 34 also includes data entries for indexing of the data element according to the doubly-linked list 36. Specifically, the data element 34 also includes an importance value (I) 50 that indicates a probability that the corresponding key entry 42 matches a specified key entry used by the search process 22 during searching throughout the doubly-linked list 36 or the tree structure 32. The data element 34 also includes a previous pointer 52 and a next pointer 54 for identifying the previous and next elements within the doubly-linked list 36, respectively. Hence, the pointers 52 and 54 enable the element 34 to maintain its proper ordering within the doubly-linked list 36, described below. Each element 34 also includes a go-to-tree flag 56, described below, that specifies a point in the linked list 36 at which the search process 22 should stop searching the doubly-linked list 36 and switch to searching using the balanced tree 32.

[0031] The data elements 34 are linked to form the doubly-linked list 36 by the background process 24 of FIG. 2, to optimize searching for the most important (i.e., most often searched) elements of the tree structure 32. As described below, the background process 24 periodically traverses the tree structure 32 to identify those elements 34 having the highest match counter values (C) over a prescribed interval. The match count values (C) are correlated to the decay factor (D) to generate an importance value (I) that identify the probability that the corresponding element 34 includes a corresponding key entry 42 that satisfies the specified key entry as a search criterion. The background process then orders the data elements 34 within the doubly-linked list 36 by descending importance values. The importance value (I) thus serves to identify the “lumpiness” of the corresponding data element 34, enabling the data elements 34 to be ordered in a sequence optimized for the lumpiness. Hence, the background process 24 serves as a means for ordering the data elements 34 according to a linked list ordering.

[0032] Once the background process 24 generates the linked list 36 with the elements 34 having an order based on descending importance values, the background process selectively sets the go-to-tree flag (F) 56 based on a determination of whether it is more beneficial to continue searching in the doubly-linked list 36, as opposed to switch to using the balanced tree pointers and search methods to continue searching for the specified key entry.

[0033] The selective setting of the go-to-tree flag (F) is based on the performance of the tree 32, namely whether a heavily-accessed data element (e.g., 34b) is deep within the tree 32, and/or whether a rarely-accessed data element is near the root node 34athe tree. As described above, a perfectly-balanced binary tree (i.e., all the elements within the tree have a random distribution that provides a uniform frequency of accesses) requires a maximum number of searches equal to log₂(n), where n is the number of elements in the tree 32. For example consider a perfectly balanced tree having a depth of 10 rows, resulting in 2¹⁰possible elements in a bottom row and a total of 2,047 elements within the tree. A perfectly balanced tree would require no more than 10 searches; however since the number of nodes at one level of a perfectly balanced tree is twice the number of nodes at the previous level, then the average number of accesses per search would actually be much closer to 9 accesses. Hence, it is unlikely that any particular heavily-accessed node will be near the top of the tree structure.

[0034] In order to balance the effectiveness of searching through the linked list 36 for the most important elements versus avoiding the addition of extra unnecessary search operations in addition to the required searches throughout the tree structure 32, the target value (T) in element 40gis determined as a “break even point” for determining at what point a doubly-linked list 36 is no longer beneficial for the search process 22 to continue searching in the doubly-linked list 36. As described below, if the search process 22, upon traversing the doubly-linked list 36, detects an element 34 having a go-to-tree flag set to true (F=1), the search process 22 discontinues searching in the doubly-linked list 36 and begins searching the tree 32, beginning with the root element 34a.

[0035] FIGS. 4A and 4B are diagrams summarizing the method by the background process 24 for linking the data elements 34 into the doubly-linked list 36 according to an embodiment of the present invention. The background process 24 is executed by the processor based system 20 at prescribed intervals, for example at prescribed time intervals such as once a second, once a minute, and the like, depending on the considerations between having an accurate doubly-linked list versus the processing requirements of the system. The method begins in step 60, where a temporary totals value (TT) is set to zero. The background process 24 then begins traversing each element 34 of the tree 32 to determine a corresponding importance value (I). Specifically, the background process 24 divides the existing corresponding importance value (I) by the decay factor (D), and adds the match counter value (C) for the corresponding element 34 to obtain the recalculated importance value (I=I/D+C) for the corresponding element 34 in step 64. Note the decay factor must be greater than one. The background process 24 then resets the corresponding match counter value to zero (C=0) in step 66, and adds the recalculated importance value to the temporary total value (TT=TT+I) in step 68. The background process then continues the recalculation of the importance values for each of the elements 34 of the tree structure 32, and adds the recalculated importance values to the temporary total value (TT).

[0036] Referring to FIG. 4B, after determining the recalculated importance values for all the elements 34 of the tree structure 32, and summing up the importance values as the temporary totals value (TT), the background process 24 calculates the target value (T) as the estimated average number of accessed elements per search in step 70. Specifically, the target value (T) is calculated based on the probability (P_x) that the search process 22 will find the element in the linked list, relative to the level (L) at which the identified elements resides within the list, plus the probability that the element is not within the linked list (1−P_x), multiplied by the possibility of searching both within the linked list and the tree structure. Since the average number of searches in a balanced tree can be expressed as log₂(E), the “break even point” can be expressed as:

[0037] log₂(E)>P_xL+(1−P_x)(L+log₂(E)),

[0038] and can be easily approximated by:

[0039] P_x>L/(log₂E).

[0040] Hence if the probability (P_x) is greater than L/(log₂E), for a given data element, then it is advantageous to continue searching using the linked list approach instead of the tree structure. This expression can be reasonably approximated in step 70 by calculating the target value (T) as equal to the sum of the temporary totals of the importance values, plus the number of misses (M), divided by 1+log₂(E).

[0041] After determining the target value, the background process 24 resets the miss counter in element 40eto zero in step 72.

[0042] The background process 24 then begins a second pass by reordering the doubly-linked list by descending importance values in steps 74. Specifically, pointers 52 and 54 in each data element 34 specify the previous and subsequent data element in the linked list 36, respectively; hence, the background process 24 adjusts the pointers 52 and 54 as necessary to change the specified order of the linked list. The background process 24 then returns to the top of the doubly-linked list in step 76, and selectively sets the go-to-tree flag in each of the elements 34 of the doubly-linked list 36 based on the corresponding importance value (I) being greater than the estimated average number (T) of accessed elements per search. Specifically, the background process checks in step 78 whether the corresponding importance value (I) is greater than the target value (T). If the importance value is greater than the target value, the background process 24 sets the go-to-tree flag to zero (F=0) in the corresponding element 34, and goes to the next descending element 34 in the doubly-linked list 36. However, if the background process 24 detects that the importance value (I) for the corresponding element 34 is less than or equal to the target value (T), indicating that it is no longer beneficial to continue searching in the doubly-linked list 36, the background process 24 sets the go-to-tree flags in the remaining descending elements 34 to (F=1) in step 82. The background process may then be repeated at prescribed time intervals in step 84.

[0043] Although the ordering of the doubly-linked list 36 and the setting of the go-to-tree flags 56 are shown as distinct steps for ease of understanding, the setting of the go-to-tree flag 56 can be set concurrently with setting the pointers 52 and 54 in the corresponding data element 34 during ordering of the doubly-linked list 36.

[0044] Once the data elements 34 have been linked to form the doubly-linked list 36 in order of descending importance values, and once the go-to-tree flags 56 have been appropriately set, the search process 22 may use the doubly-linked list 36 for searching for specified key elements. For example, FIG. 5 is a flow diagram illustrating the method used by the search process 22 for searching for a specified key entry. The search process 22 begins searching for the specified key entry using the doubly linked list 36 in step 90. Since the top of the doubly-linked list 36 (e.g., element 34b) has the key entry 42 that corresponds to the highest searched element, there tends to be a higher probability that the search process 22 will find the element corresponding to the specified key entry within the first few elements using the doubly-linked list as an index for the search. As described previously, this bypass of the tree structure 32 as an index can provide substantial savings if the distribution of elements within the tree structure 32 locates heavily-accessed elements (e.g., 34b) near the bottom of the tree.

[0045] If the search process 22 determines in step 92 that the go-to-tree flag indicator is set to one as it traverses the doubly-linked list 36, the search process 22 begins searching of the tree structure 32 for the specified key entry in step 96. Alternatively, if the corresponding element in the doubly-linked list 36 does not have to go-to-tree flag set to 1, the search process 22 continues searching in the next element of the doubly-linked list in step 94. Hence, searching for a specified key entry can be dramatically improved where the tree structure 32 has a relatively large number of elements and the tree structure is substantially unbalanced. For example, FIG. 3A illustrates that a search process 22 would locate data element 34cwithin two search operations using the doubly linked list 36, and five search operations using the tree structure 32; hence, the go-to-tree flag 56 for element 34cwould be set to 0. Searching for the data element 34d, however, would require three search operations using the doubly-linked list 36 and four search operations using the tree structure 32; moreover, searching for the data element 34ewould require more search operations if the doubly-linked list 36 was used. Hence, the go-to-tree flag 56 for data element 34cwould probably be set to 1.

[0046] FIGS. 6A and 6B illustrate methods used by the element insertion/removal process 26 to add or delete elements from the tree. As a new element is added to the tree 32 by the element insertion process 26 in step 100, the insertion process 26 also adds the new element at the bottom of the linked list in step 102 by setting the next pointer 54 of the previous last element to point to the new last element. The element insertion process then sets the importance value for the new element to zero, the match counter value to 1, and the go-to-tree flag to 1 in step 104, and increments the element counter 40din step 106.

[0047] If an element 34 is to be deleted from the tree structure 32, the removal process 26 deletes the element 34 from the tree in step 108 by resetting the pointers 46 and 48 for the upper element; the removal process 26 removes the element from the linked list in step 110 by resetting the previous and next pointers 52 and 54 accordingly, and decrements the element counter 40d.

[0048] According to the disclosed embodiment, search techniques in a processor-based system may be dramatically improved without the necessity of performing tree rotation for an existing tree structure where heavily-accessed data elements are in the middle or bottom of a tree. Rather, the data elements may be linked to enable searching using a doubly-linked list to optimize search performance for heavily-accessed data elements.

[0049] While this invention has been described in connection with what is presently considered to be the most practical and preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.