Prefix search tree partial key branching

Claim 1

A computer-implemented method for searching an information tree of record keys with a search key to locate and retrieve one of a plurality of data records of a database held in the memory of a data processing system, wherein: each of said record keys represents one of said data records and comprises a string of a plurality ("s") of characters, the number s of said characters differing for different ones of said record keys; said search key comprises a string of a plurality ("k") of characters; and said tree comprises a plurality of linked information nodes held in said memory, wherein each of at least some of said nodes comprises: (i) a first field holding a string of the i-th through p-th successive characters common to the all of the record keys represented by all of at least one subtree of said each of at least some of said nodes; (ii) a second field holding a pointer to a data record for which said i-th through p-th successive characters represent a final portion of the respective record key; and (iii) a third field for each of said at least one subtree of said node and holding a (p+1)st record key character immediately following said pth character held in said first field, which (p+1)st record key character is common to all of the record keys represented by the respective one of said at least one subtree, said third field including a respective pointer to the root node of said respective one of said at least one subtree; said method being characterized by: .0. for each one of said nodes, comparing the string of the i-th through p-th successive characters of said search key with the record key character string held in the first field of said node, and (1) if said search key string does not match said record key string, terminating said method, but (2) if said search key string matches said record key string, then (a) if k=p, retrieving from the memory a data record using the pointer held in the second field of said node, but (b) if k>p, comparing the (p+1)st search key character with the (p+1)st record key character held in each of the third fields of said node, and (i) if said (p+1)st search key character does not match any of said (p+1)st record key characters, terminating said method, but (ii) if said (p+1)st search key character matches one of said (p+1)st record key characters, then retrieving from the memory the root node for the respective subtree using the pointer held in the respective third field of the node holding said (p+1)st record key character, and returning to step .0. to continue said method for the root node so retrieved.