Patent ID: 6941314
Filing Date: 2005-09-06
Classification: G06F,Y10S

Abstract:
1. A computer-implemented method of editing a sorted tree data structure comprising: selecting a minimum number of entries and a maximum number of entries in each vertex of the sorted tree data structure wherein each entry includes an entry address, a key address, a child vertex address, and a child vertex index for determining a tradeoff between memory utilization and required execution time; if inserting an entry into a bottom vertex of the sorted tree data structure exceeds the maximum number of entries in the bottom vertex, and if another bottom vertex has fewer than the maximum number of entries, then redistributing entries in the sorted tree data structure until no bottom vertex has more than the maximum number of entries and no bottom vertex has fewer than the minimum number of entries; if inserting an entry into the bottom vertex exceeds the maximum number of entries, and if no bottom vertex has fewer than the maximum number of entries, then creating a new bottom vertex in the sorted tree data structure and redistributing entries in the sorted tree data structure until no bottom vertex has more than the maximum number of entries and no bottom vertexs has fewer than the minimum number of entries; if deleting an entry from the bottom vertex results in fewer than the minimum number of entries, and if another bottom vertex has more than the minimum number of entries, then redistributing entries in the sorted tree data structure until no bottom vertex has fewer than the minimum number of entries and no bottom vertex has more than the maximum number of entries; and if deleting an entry from the bottom vertex results in fewer than the minimum number of entries, and if no remaining bottom vertex has more than the minimum number of entries, then redistributing the entries in the sorted tree data structure until the bottom vertex has no entries and deleting the bottom vertex so that every remaining bottom vertex in the sorted tree data structure has no fewer than the minimum number of entries and no more than the maximum number of entries.