PREFIX SEARCH TREE PARTIAL KEY BRANCHING

A prefix index tree structure for locating data records stored through keys related to information stored in data records. Each node includes a prefix field for a prefix string of length p of the longest string of key characters shared by all subtrees of the node and a data record field for a reference to a data record whose key is completed by the prefix string. A node may include one or more branch fields when the prefix string is a prefix of keys stored in at least one subtree of the node, with a branch field for each distinct p+1.sup.st key character in the keys, wherein each p+1.sup.st key character is a branch character. Each branch field includes a branch character and a branch pointer field for a reference to a node containing at least one key whose p+1.sup.st character is the branch character. Each node further includes a field for storing the number of key characters in the prefix string and a field for storing the number of branch fields in the node. Also disclosed are methods for constructing and searching a prefix index tree of the present invention, and for inserting nodes into the tree and deleting nodes from the tree.