Patent ID: 6735600
Filing Date: 2004-05-11
Classification: G06F,Y10S

Abstract:
A process for changing the number of entries in a search tree having a top level, a bottom level and at least one intermediate hierarchy level between the top level and the bottom level, the bottom level containing a plurality of entries distributed among a plurality of vertices so that each vertex of the bottom level contains at least one entry, each bottom level vertex being a child vertex to a vertex of a higher level and each vertex in the top and intermediate hierarchy levels being a parent to at least one vertex in a lower level, the at least one intermediate hierarchy level containing a plurality of entries distributed in at least one vertex, each vertex in at least each intermediate hierarchy and bottom levels having an index, the process comprising steps of:a) selecting a vertex in a level other than the bottom level and identifying the level of the selected vertex; b) iteratively redistributing entries between the descendant vertices of the selected vertex on a level so that the descendant vertex having a maximal index contains a predetermined number of entries, each iteration using the descendant vertex having the maximal index found during one iteration for the selected vertex during the next iteration, until a descendant vertex is found in the bottom level; and c) inserting or deleting an entry on the descendant vertex having the maximal index.