Patent ID: 6490592
Filing Date: 2002-12-03
Classification: G06F,Y10S

Abstract:
A method of inserting a new data element into a data structure comprised of a plurality of records that includes at least a root record, each of said plurality of records including at least one node and at least one pointer that points to another of said plurality of records or to a null value, said at least one node being capable of storing a respective one of a plurality of data elements, each of said plurality of data elements and said new data element including a prefix that represents at least one address value and associated data, said prefix being comprised of an address portion and a prefix length portion which defines the number of bits in said prefix, at least a portion of said data structure being arranged substantially as a balanced tree; said method comprising the steps of:forming the data structure by merging at least one L-structure into a B-tree structure, the L-structure and the B-tree structure being formed independently of each other, the B-tree structure having non-overlapping ones of prefixes, the L-structure having overlapping ones of prefixes, the L-structure having a set in which at least one of the overlapping prefixes contains at least one of a succession of the overlapping prefixes; locating a node in a respective one of said plurality of records having a prefix that is identical to said prefix of said new data element; and replacing associated data stored in said node of said respective one of said plurality of records with said associated data of said new data element.