Abstract:
A method and apparatus for storage, insertion, deletion, and searching of a database index using a compact representation of a 0-complete binary tree. The compact representation, termed a C 0 -trie, is represented in a computer memory as a set of layered vectors with the layering of the vectors corresponding to the depths of the C 0 -trie. Insertion and deletion processes maintain the representation of the C 0 -trie remains in a well-formed and taut state at the end of each operation, thus providing subsequent efficient manipulations of the C 0 -trie in computer memory.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    The invention relates to computer data and file storage systems, and more particularly to a method and system for inserting and deleting search keys from a structure implementing a compact representation of a 0-complete binary tree.  
           [0002]    Data and file storage systems such as a database, in particular those implemented in computer systems, provide for the storage and retrieval of specific items of information stored in the database. The information stored in the database is generally indexed such that any specific item of information in the database may be located using search keys. Searches are generally accomplished by using search keys to search through an index to find pointers to the most likely locations of the information in the database, whether that location is within the memory of the computer system or in a storage medium of the computer system.  
           [0003]    An index to database records within a computer is sometimes structured as a “trie” comprised of one or more nodes, connected hierarchically, stored within a storage means of the computer. A trie is a tree structure designed for storing strings in which there is one node for every common prefix. The actual strings are stored at the “bottom” of this hierarchical structure in leaf nodes. Each node generally includes one or more branch fields containing information for directing a search, and each such branch field usually contains a pointer, or branch, to another node, and an associated branch key indicating ranges or types of information that may be located along that branch from the node. The trie, and any search of the trie, begins at a single node referred to as the root node and progresses downwards through the various branch nodes until the nodes containing either the items of information or, more usually, pointers to items of information are reached. The information related nodes are often referred to as leaf nodes or, since this is the level at which the search either succeeds or fails, failure nodes. Within a tree storage structure of a computer, any node within a trie is a parent node with respect to all nodes dependent from that node, and sub-structures within a trie which are dependent from that parent node are often referred to as subtries with respect to that node.  
           [0004]    The decision as to which direction, or branch, to take through a tree storage structure in a search is determined by comparing the search key and the branch keys stored in each node encountered in the search. The results of the comparisons to the branches descending from a given node are to be followed in the next step of the search. In this regard, search keys are most generally comprised of strings of characters or numbers which relate to the item or items of information to be searched for within the computer system.  
           [0005]    The prior art contains a variety of search tree data storage structures for computer database systems, among which is the apparent ancestor from which all later tree structures have been developed and the most general form of search tree well known in the art, the “B-tree.” See, for example, Knuth,  The Art of Computer Programming , Vol. 3, pp. 473-479. A B-tree provides both primary access and then secondary access to a data set. Therefore, these trees have often been used in data storage structures utilized by database and file systems. Nevertheless, there are problems that exist with the utilization of B-tree storage structures within database systems. Every indexed attribute value must be replicated in the index itself. The cumulative effect of replicating many secondary index values is to create indices which often exceed the size of the database itself. This overhead can force database designers to reject potentially useful access paths. Moreover, inclusion of search key values within blocks of the B-tree significantly decreases the block fan out and increases tree depth and retrieval time.  
           [0006]    Another tree structure which can be implemented in computer database systems, compact 0-complete binary trees (i.e., O-trees), eliminates search values from indices by replacing them with small surrogates whose typical 8-bit length will be adequate for most practical key lengths (i.e., less than 32 bytes). Thus, actual values can be stored anywhere in arbitrary order, leaving the indices to the tree structure to be just hierarchical collections of (surrogate, pointer) pairs stored in an index block. This organization can reduce the size of the indexes by about 50% to 80% and increases the branching factor of the trees, which provides a reduction in the number of disk accesses in the system per exact match query within computer database systems. See Orlandic and Pfaltz,  Compact  0- Complete Trees, Proceedings of the  14 th VLDB Conference , pp. 372-381.  
           [0007]    While the known method of creating C 0 -trees increases storage utilization 50% to 80% over B-trees, there still remains a waste of storage space because of the presence of dummy entries (surrogate, pointer==NIL) wherein the number of index entries at the lowest level of the tree exceeds the actual number of records stored. Therefore, the expected storage utilization of index entries of C 0 -trees at the lowest tree level is 0.567 versus 0.693 as in the case of B-trees. See Orlandic and Pfaltz,  Compact  0- Complete Trees, Proceedings of the  14 th VLDB Conference , pp. 372-381.  
           [0008]    Moreover, although B-trees and O-tree storage structures represent efficient methods of searching for values, both methods require initial generation and subsequent maintenance of the tree data storage structure itself. Neither of these computer storage structures inherently stores information in sorted order.  
           [0009]    A trie can be built more efficiently if the key records are initially sorted in the order of their key field, than if records are in random order. Therefore, an efficient computer database system should sort sets of keys first, and then build a trie based on keys extracted at intervals from the sorted keys. Searches of the tree data storage structure will also be performed more efficiently if the trie does not contain an excess number of keys, namely keys that are associated with data no longer in the database or keys that are no longer necessary to maintain the structure of the trie. In some implementations of O-tree storage structures, the method of storing and indexing the search keys may be complex, and the method of inserting and deleting groups of keys may be inefficient. Therefore, a need exists to simplify the trie structure and to easily delete and insert groups of keys in batches is desirable, especially when large groups of keys are involved.  
         SUMMARY OF THE INVENTION  
         [0010]    A method and apparatus for storage, insertion, deletion, and searching of a database index using an O-tree is provided. The O-tree is represented in a computer memory as a set of layered vectors with the layering of the vectors corresponding to the depths of the O-tree. This representation of the O-tree is termed a “C 0 -trie.” Insertion and deletion processes maintain the C 0 -trie in a well-formed and taut state at the end of each operation, thus providing subsequent efficient manipulations of the C 0 -trie in computer memory.  
           [0011]    In one aspect of the invention, a C 0 -trie, includes a depth vector having encoded depth values for depths of leaves of an O-tree. The depth vector is encoded to show whether or not the corresponding leaf is an empty leaf node and is of arbitrary length. A set of selector vectors, grouped in a compound vector, corresponds to the levels of the C 0 -trie. Each selector vector is a vector used to select entries of the depth vector. As with the length of the depth vector, the number of selector vectors in the set of selector vectors is arbitrary. Each selector vector is paired with a counter vector from a set of counter vectors grouped in a compound vector. The counter vector is a vector whose length is equal to the number of 1-bits in the corresponding selector vector.  
           [0012]    Values in the C 0 -trie can be referred to by their position within the tree. This position identifier is a surrogate for the value that can be efficiently encoded in a bit vector. Since the C 0 -trie organizes values in lexical order, the position identifier is a lexical identifier.  
           [0013]    In another aspect of the invention, for any level l subtrie A of the C 0 -trie, and its level l predecessor B, the depths of all the level l- 1  subtries of A are greater than the depths of A and B (called well-formed), and values or strings in the C 0 -trie are distinguished by the shortest possible prefixes by having no unnecessary empty nodes included in the leaves of the subtries (called taut).  
           [0014]    In another aspect of the invention, a search process is provided for the computer implemented C 0 -trie. The search process includes searching depths of the top-1 search level subtries for each subtrie in a next level beneath a top search level. The depth values selected by the top-1 search level selector vector are examined and if the value is not identified as being part of the current top-1 search level subtrie, the search process determines if there are any remaining top-1 level subtries to search. If there are not any remaining top-1 level subtries to search, the search process terminates. If there are more top-1 level subtries to search, the search process continues searching the remaining top-1 level subtries. When the search process identifies a top-1 search level subtrie including the searched for value, the search process descends one level by making the current top-1 search level the top search level and the identified top-1 search level subtrie an identified top search level subtrie. Finally, the search process determines if a new top search level is a leaf selector level and if not, continues searching the top-1 search level subtries of the identified top search level subtrie.  
           [0015]    In another aspect of the invention, a delete process is provided for the computer implemented C 0 -trie. The delete process receives a list of lexical identifiers or tokens to delete. If the number of lexical identifiers to be deleted exceeds a threshold value, the delete process generates a new C 0 -trie using lexical identifiers remaining in the C 0 -trie. If the number of lexical identifiers to be deleted does not exceed the threshold value, the delete process deletes leaves in the C 0 -trie including the lexical identifiers. Otherwise, the delete process traverses a branch of the C 0 -trie including a lexical identifier to be deleted and deletes the lexical identifier from the branch of the C 0 -trie. If the remaining C 0 -trie has more than two levels, then the delete process examines the C 0 -trie and merges subtries of the C 0 -trie.  
           [0016]    In another aspect of the invention, an insert process for the computer implemented C 0 -trie includes receiving values to insert and determining if the C 0 -trie has two levels. If so, then while there are values to insert, the insert process identifies a key interval in an existing leaf of the C 0 -trie to which a value belongs and inserts one or more values into the identified key interval. Once the insert process has completed inserting values, the insert process splits a subtrie of the C 0 -trie if the subtrie includes new values that have a depth less than or equal to the depth of the subtrie.  
           [0017]    In another aspect of the invention, the insert process further includes the ability to process a C 0 -trie having more than two levels. While there are values to insert, the insert process traverses a branch of the C 0 -trie by iteratively performing the following: while a selected level immediately below the current level is not the level above a leaf level, the insert process recursively determines which level immediately below the current level includes a subtrie of the C 0 -trie whose key interval includes a value and select as the determined subtrie. Once the insert process traverses the branch of the C 0 -trie, the insert process identifies a key interval in an existing leaf to which a value belongs and inserts one or more values into the identified key interval. The insert process then splits the subtrie if the subtrie includes new values that have a depth less than or equal to the depth of the subtree. After all values have been inserted, the insert process examines the C 0 -trie for further splitting. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0018]    These and other features, aspects, and advantages of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where:  
         [0019]    [0019]FIG. 1 a  is a block diagram of a data processing system in accordance with an exemplary embodiment of the present invention;  
         [0020]    [0020]FIG. 1 b  is a schematic and block diagram of a database system in accordance with an exemplary embodiment of the present invention;  
         [0021]    [0021]FIG. 2 a  is a conceptual illustration of a complete binary tree;  
         [0022]    [0022]FIG. 2 b  is a conceptual illustration of a 0-complete binary tree;  
         [0023]    [0023]FIG. 3 a  is a diagram of a O-tree index structure for values stored in a database;  
         [0024]    [0024]FIG. 4 a  illustrates an instantiation of a O-tree;  
         [0025]    [0025]FIG. 5 is a block diagram depicting a data structure used to represent a C 0 -trie in accordance with an exemplary embodiment of the present invention;  
         [0026]    [0026]FIG. 6 is a block drawing depicting an illustrative instance of a C 0 -trie&#39;s selection vectors in accordance with an exemplary embodiment of the present invention;  
         [0027]    [0027]FIG. 7 is a process flow diagram of a C 0 -trie search process in accordance with an exemplary embodiment of the present invention;  
         [0028]    [0028]FIG. 8 is a block diagram of a value storage structure in accordance with an exemplary embodiment of the present invention;  
         [0029]    [0029]FIG. 9 is a process flow diagram of a deletion process in accordance with an exemplary embodiment of the present invention;  
         [0030]    [0030]FIG. 10 is a process flow diagram of a C 0 -trie merge control process in accordance with an exemplary embodiment of the present invention;  
         [0031]    [0031]FIG. 11 is a process flow diagram of a C 0 -trie merge process as used in an exemplary embodiment of the present invention;  
         [0032]    [0032]FIG. 12 is a process flow diagram of a branch delete process in accordance with an exemplary embodiment of the present invention;  
         [0033]    [0033]FIG. 13 is a process flow diagram of an insertion process in accordance with an exemplary embodiment of the present invention;  
         [0034]    [0034]FIG. 14 is a process flow diagram of a branch insertion process in accordance with an exemplary embodiment of the present invention;  
         [0035]    [0035]FIG. 15 is a process flow diagram of a C 0 -trie rebuilding process in accordance with an exemplary embodiment of the present invention;  
         [0036]    [0036]FIG. 16 is a process flow diagram of a subtrie depth determination process as used by a C 0 -trie rebuilding process in accordance with an exemplary embodiment of the present invention; and  
         [0037]    [0037]FIG. 17 is a process flow diagram of a dummy placement process as used by a C 0 -trie rebuilding process in accordance with an exemplary embodiment of the present invention. 
     
    
     DETAILED DESCRIPTION  
       [0038]    [0038]FIG. 1 a  depicts a data processing system having a programmable computer and computer programs for creating a file system and for processing operations on the file system in accordance with an exemplary embodiment of the present invention. The computer system includes programmable computer  1  having a processor and a memory, display  2 , computer input device  3 , and a storage means. The storage means includes a storage device  4  such as a magnetic disk storage system or a partition of the memory of the computer for storage of data. Hardware/and software including the file system and hardware/and software including program instructions executable by the processor for performing processing operations to be described are implemented in a file system  5  (shown in phantom lines), of computer  1 . File system  5  of computer  1  coordinates the various activities related to representing data in the file system and to performing operations on one or more data files stored within the storage device  4 . Computer  1  can be a programmed general purpose computer, such as a personal, mini or mainframe computer, or a special purpose computer formed by one or more integrated chips.  
         [0039]    Referring to FIG. 1 b , file system  5  includes a file processing unit  7  and a command interpreter  6 . In order to access specific items of information stored in the computer file system, the file processing unit  7  uses a compact 0-complete data storage structure  40  as depicted in FIG. 4 a  for minimizing the amount of information required to retrieve items of data stored within the storage device  4 . The data storage structure has a plurality of entries  30 ,  31 ,  80 ,  81 ,  82 ,  83 ,  84 ,  85 ,  86 ,  87 ,  88  for indexing search keys  1420 , wherein each entry comprises a depth value  89  and a data present indicator  90 , the latter, by way of example having two conditions, and a novel C 0 -trie structure  43  stored in the storage device  4  of the computer interconnecting the entries and forming the data storage structure  40 . The data storage structure  40  further includes a means  66  for storing the count of the non-NIL leaf entries associated with a search key interval range. In addition, there are separate pointers structure comprised of header  36  and entries  36   a , that is distinct from the trie structure  43  and, in a typical embodiment, may be distinct from the data storage structure  40  itself. The pointers structure  36  and  36   a  accesses the data items within the storage container  39  of the storage device  4 .  
         [0040]    Referring to FIG. 2 a , binary tree  1402  is an illustrative edge labeled tree data storage structure consisting of nodes indicated by dots, such as  1406 ,  1408  and  1410 , separated by arcs or edges, such as  1412  and  1414 . The nodes are identified by small and capital letters a through Z and A′. The end nodes are called leaf nodes or leafs and are labeled with capital letters. All the other interior nodes are labeled with small letters. Information to be retrieved is stored in storage locations pointed to by pointers located at the tree&#39;s leaves, such as leaves  1416  and  1418 . Search keys  1420  are shown for leaves H, I, V, W, L, Z, A′ and Q. In FIG. 2 a , the search keys  1420  are strings of binary digits with an arbitrary, uniform length up to some maximum length in bits, 8 bits being used by way of example. The search keys  1420  associated with each of these leaves are used to locate the pointer to the storage location for the corresponding leaf in the storage device  4 . Only those leaves indicated by an associated search key  1420  have a pointer to a storage location that stores associated data records and therefore are said to be full. The leaves G, K,  0 , S, T and Y do not have pointers to a storage location and therefore are said to be empty.  
         [0041]    Retrieval of the data records in the storage device  4  is achieved by successively comparing binary 0 and 1 symbols in one of the search keys  1420  with a 0 or 1 edge label on each arc  1412  between the nodes along a path of the connected dots and arcs starting with root node a and ending with the desired leaf. Each node or leaf of the binary tree is either a 0-node or 0-leaf if its entering arc is labeled 0, or a 1-node or 1-leaf if its entering arc is labeled 1. In a computer database and file management system, an access path to a node is a binary string obtained by concatenating the 0 and 1 edge labels traversed from the root node a to the particular node in question.  
         [0042]    Binary tree structures are said to be “complete” if every node is either a leaf or is a node that has exactly two non-empty direct descendants (i.e., nodes having a dependent 0-node and a dependent 1-node). In FIG. 2 a , each node from node a to node A′ satisfies the two conditions for completeness.  
         [0043]    Thus, FIG. 2 a  depicts a tree storage structure with the search keys  1420 , including 00001000, 00100101, 01000010, 01000110, 1000001, 10101000, 10101010 and 10110010, to locate data records at leaves H, I, V, W, L, Z, A′ and Q respectively. Empty leaves G, K,  0 , T, S and Y are included within the tree  1402  to fulfill the requirement of a “complete” binary tree.  
         [0044]    Refer now to FIG. 2 b . A prior art 0-complete binary tree  1430  is shown having the same structure, nomenclature and reference numerals as used in FIG. 2 a  except where noted. Binary tree  1430  with δ leaves is said to be 0-complete if 1) the sibling of any 0-leaf is present in the tree, and 2) there are exactly δ-1 1-nodes in the tree. Thus, FIG. 2 b  is a 0-complete binary tree representation of the binary tree of FIG. 2 a  since every 0-leaf H, V, L, T, Z has a sibling 1-node, and there are nine leaves H, I, V, W, L, T, Z, A′ and Q and eight 1-nodes I, W, e, c, m, A′, U and Q. The 0-complete binary tree  1430  is derived from the binary tree  1402  of FIG. 2 a  by deleting from the tree  1402  those 1-leaves that are empty (indicated by the lack of an associated search key) such as leaves G, K,  0 , S and Y. Note that deletion of any empty 0-leaf violates the second condition which requires eight 1-nodes in tree  1430 , so that node T, even though it is empty, remains in the tree storage structure  1430  and increases required storage space.  
         [0045]    Each interior node, designated by small letters, has a corresponding 0-subtree and 1-subtree. The “pre-order traversal” of an 0-complete binary tree starts at the root node a of the tree and then iterates the following two steps until the last node has been accessed:  
         [0046]    (1) if the current node nni is an internal node then the next node nn i+1  in the order will be its 0-son because, by definition of 0-completeness, every interior node must have a 0-son node;  
         [0047]    (2) if the current node nn i  is a leaf then the next node in the pre-order will be the 1-son of the node pp whose 0-subtrie contains nni and whose depth is maximal.  
         [0048]    Thus, the first node in pre-order is the internal root node a. The next node is its 0-son node b, which is followed by 0-son nodes d and then leaf H. The next node in pre-order is the 1-son of the node d since H is a leaf node and the 0-subtrie of node d contains H and its depth in the tree is maximal (i.e., depth of 2 as opposed to node b whose 0-subtrie contains H and whose depth is 1). The complete pre-order traversal of tree  1430  depicted in FIG. 2 b  is the sequence a b d H I e j n r V W c f L m p T u x Z A′ Q.  
         [0049]    Successor nodes to each leaf node H, I, V, W, L, T, Z, A′ except the last leaf node Q in the pre-order traversal of a 0-complete binary tree are also of special importance. These nodes, termed bounding nodes, are respectively I, e, W, c, m, u, A′, Q in FIG. 2 b . Since bounding nodes are defined in terms of the pre-order traversal, each leaf node, except the last one Q, has its own unique bounding node. In addition, from the previously stated definition of the pre-order traversal, every bounding node is a 1-node. “Discriminators” of a node and a bounding node can be used to establish a key interval that corresponds to each leaf in the 0-complete binary tree. The “discriminator” of a leaf node is a binary string of the same length as the search keys and whose high order, or left-most, bits are the binary bits of the concatenated arcs, or path, leading up to the leaf with all of the other right-most bits set to 0.  
         [0050]    The “key interval” is formally defined to be the key range between the leaf discriminator (inclusively) and the discriminator of its bounding node (non-inclusively). The exception is again the last leaf (Q by way of example) in the pre-order traversal, whose upper bound of its key interval is always known in advance and consists of all one bits (i.e., 11111111).  
         [0051]    In Table 1 below, the key intervals of each leaf node H, I, V, W, L, T, Z, A′, Q of the 0-complete binary tree  1430  are listed in lexicographic order. Thus, for example, leaf V has a discriminator of 01000000 and its corresponding bounding node W has a discriminator 01000100; the key interval of leaf V, as shown in Table 1, is 01000000 (inclusive) to 01000100 (non-inclusive), or 01000000 to 01000011 inclusively.  
                               TABLE 1                                       Key Interval   Bounding Node           Leaf   of Leaf Node   Node - Depth                           H   00000000-00100000   I - 3           I   00100000-01000000   e - 2           V   01000000-01000100   W - 6           W   01000100-10000000   c - 1           L   10000000-10100000   m - 3           T   10100000-10101000   u - 5           Z   10101000-10101010   A′ - 7           A′   10101010-10110000   Q - 4           Q   10110000-11111111   -0                      
 
         [0052]    By examining Table 1, knowledge of bounding node discriminators is sufficient to identify the appropriate key interval of any leaf and hence the corresponding data record with any given search key. By way of example using search key 01000010, a search procedure that examines the bounding discriminators of the tree in their pre-order traversal sequence will find the correct key interval for the search key when the first bounding discriminator greater than the search key 01000010 is found. The discriminator of the first bounding node I, 00100000, is less than the search key 01000010. The second bounding discriminator of bounding node e in pre-order, 01000000, is also less than the search key. The discriminator of the third bounding node W. 01000100, is greater and is the non-inclusive upper bound of the key interval for leaf V. The inclusive lower bound of the key interval for leaf V is the discriminator of the previous bounding node e.  
         [0053]    Along with each key interval in Table 1, there is shown a number denoting the “depth” of the bounding node in the 0-complete binary tree  1430  for that key interval. For example, the bounding node of leaf V is the leaf W that has a depth of 6 in the 0-complete binary tree. For the last node Q, which has no bounding node by definition, the upper bound of its interval is set to 11111111 with an assigned depth of 0.  
         [0054]    There is one apparent regularity in the relationship between discriminators of a set of bounding nodes and their depths. If the depth of a bounding node is dd, then by definition of a discriminator, the dd th  bit of the corresponding discriminator is set to 1 with all subsequent lower order bits 0.  
         [0055]    In Table 1 wherein the key length is eight bits, the initial dummy discriminator is 00000000 and the depth of the first bounding node I is three, the third bit of the first bounding node discriminator is 1 and all subsequent, low order bits are 0 to obtain the first bounding node discriminator 00100000; the depth of the second bounding node e is two, using the first bounding node discriminator, the second bit is set to 1 and all subsequent bits are set to 0 in order to obtain the second bounding node discriminator 01000000. The discriminators of the remainder of the bounding nodes are constructed in a similar manner.  
         [0056]    Using the knowledge that key intervals can be constructed from depths of bounding nodes in a 0-complete binary tree, a prior art compact form of the 0-complete binary tree data structure of FIG. 2 b  is represented at  9  in FIG. 3 a . This compact form is called an O-trie. The trie structure has index blocks  10 ,  11 , and  12  with entries  17 .  
         [0057]    Now, referencing FIG. 4 a , a representation of the data storage structure  40  is depicted after the input of a set of search keys  1420  of FIG. 2 a . A greater number of search keys can be input into the data storage structure  40 , and it would be within the skill of the practitioner in the art to apply the described embodiment to a greater set of keys. As opposed to the C 0 -trie of FIG. 3 a  having blocks  10 ,  11  and  12  with adjacent depth value  17   a  and pointer  17   b  entries  17 , the data storage structure of FIG. 4 a  has a trie structure  43  comprised of a root node  47  with an index block header  47   a  indexed to index block entries  47   c  and subtrie pointer  47   b , a node  34  with an index block header  34   a  linked to index block entries  34   c  and subtrie pointer  34   b , and node  35  with index block header  35   a  linked to index block entries  35   c  and subtrie pointer  35   b.    
         [0058]    Each entry in  47   c ,  34   c  and  35   c  contains a depth value  89  and a data present indicator  90 . In addition, the structure  40  has a separate pointers structure comprised of a pointers header  36  with corresponding entries  36   a  containing the pointers or referencable indices for the corresponding depth values  89  of leaf index block entries  34   c  and  35   c  that are non-NIL. The depth values  89  in  34   c  and  35   c  and the indices of pointer entries  36   a  are representative of the depth values  17   a  and pointers  17   b  in index blocks  11  and  12  of FIG. 3 a , except that empty pointers corresponding to 0-leaf entries, thereby reducing wasted storage space. The index block entries  47   c  of node  47  includes entries  30  and  31 , corresponding to the entries in index block  10  of FIG. 3 a  which give the last, i.e., minimum value depth entries in the corresponding index blocks of  34   c  and  35   c , respectively. Pointer  47   b  of the root level  41  points to the leaf level  64  for key intervals corresponding to each of the index block entries  47   c.    
         [0059]    In addition to separation of the corresponding depth values  89  into index block entries  47   c ,  34   c  and  35   c  and pointer entries  36   a , counts header  66  with corresponding entries  66   a  is related. Entries  66   a  contains count entries  32  and  33  that give the total number of F or full leaf (non-NIL) entries in index block entries  34   c  and  35   c , respectively. Thus, count entry  32  has a value of 4 indicating there are 4 non-NIL 4 entries (or F values) in index block entries  34   c . Count entry  33  has a value of 4 indicating there are 4 non-NIL entries (or F values) in index block entries  35   c . Thus, the data storage structure  40  has a novel O-trie structure  43 , a distinct pointers structure  36  and  36   a , and a storage container  39 . The nodes  34 ,  35  and  47  and the counts header  66  and counts entries  66   a  are in the trie structure  43  whereas the referencable indices or pointers are in the separate pointers structure comprised of header  36  and entries  36   a.    
         [0060]    The trie structure  43  in the FIG. 4 a  example has a height of two, root level  41  and leaf level  64 . Index block entries  47   c  at root level  41  include two entries  30  and  31 , and index block entries structures  34   c  and  35   c  at leaf level  64  include four entries  80 ,  81 ,  82 ,  83  and five entries  84 ,  85 ,  86 ,  87 ,  88 , respectively. The height or number of levels of an O-trie storage structure varies depending on the number of data items and associated search keys to be indexed within the leaf entries of the trie structure  43  and on a predetermined full index block number  79  set within the file system. The described FIG. 4 a  example embodiment has a predetermined full index block number  79  of five.  
         [0061]    Depth values  89  are located in index block entries  47   c ,  34   c ,  35   c  that are linked by index block headers  47   a ,  34   a  and  35   a  within the nodes  47 ,  34  and  35 , respectively, of trie structure  43 . Pointer entries  36   a  are linked to trie structure  43  by pointers header  36 . Significantly, the data present indicator bit  90  is also in each of the index block entries  47   c ,  34   c  and  35   c.    
         [0062]    Each indicator bit  90  is in one of two conditions, FALSE or TRUE, represented by 0 and 1, respectively. In depth values  89  at the leaf level  64 , a TRUE or first condition, indicates that the corresponding entry is a NIL entry of the C 0 -trie or empty node of a conceptual 0-complete binary tree. A FALSE, or second condition, indicates the corresponding entry is associated with a corresponding data item in the storage device of the computer. Each of the non-NIL entries  80  to  84  and  86  to  88  has a corresponding data item within the storage container  39  of memory  8  of the computer which is addressed by means of one of the pointer entries  36   a . A NIL or TRUE entry such as  85  does not address any index entry in  36   a  or data item in the storage container  39 . Each of the pointer entries  36   a  is a pointer or a referencable index to the corresponding lexically ordered data item, or alternatively to one of the search keys  1420  which is associated with the data item, stored within the storage device of the computer.  
         [0063]    [0063]FIG. 5 is a drawing depicting a data structure used to represent a C 0 -trie in accordance with an exemplary embodiment of the present invention. A C 0 -trie data structure  500  has three parts: (1) a depth vector  502 , (2) a set of selector vectors  508 , and (3) a set of counter vectors  518 .  
         [0064]    A depth vector is a vector including encoded depth values, such as encoded depth value  504 , for the depths of the leaves of the implemented C 0 -trie, encoded to show whether or not the corresponding leaf is a dummy. For example, the nth entry of the depth vector is the encoded depth of the nth leaf. If d is the depth of a leaf, then the encoded depth is 2d if the leaf is not a dummy leaf and 2d+1 if it is a dummy leaf. The depth vector is of arbitrary length as indicated by ellipses  506 .  
         [0065]    The C 0 -trie data structure further includes a compound vector  508 , herein termed a selector parent, of selector vectors. Each selector vector, such as selector vector  510 , corresponds to a ‘level’ of the C 0 -trie. Each selector vector is a vector used to select entries of the depth vector and is of arbitrary length, as indicated by ellipses  511 . The number of selector vectors in the selector parent is arbitrary, as indicated by ellipses  516 . A bottom-most selector vector, such as selector vector  514 , is herein termed a “leaf selector vector”. A topmost selector vector, such as selector vector  517 , is herein termed a “top selector vector.” As the selector parent is of arbitrary length, the number of selector vectors is also arbitrary. Therefore, any C 0 -trie of arbitrary depth may be represented.  
         [0066]    The C 0 -trie data structure further includes a compound vector  518 , herein termed a counter parent, of counter vectors. Each selector vector (and hence each level in the C 0 -trie) has paired with it a corresponding counter vector, such as counter vector  520 . As the number of selector vectors is arbitrary, the number of counter vectors, and hence the length of the counter parent, is arbitrary as indicated by ellipses  519 . A counter vector is a vector whose length is equal to the number of “1-bits” in the corresponding selector vector. As the size of the selector vectors is arbitrary, so is the size of the counter vectors as exemplified by ellipses  521 . The nth entry of the counter vector, such as entry  522 , is the number of non-empty leaves contained in the nth subtrie designated by the selector vector.  
         [0067]    There are two properties that are maintained in the C 0 -trie data structure. (1) For any level l subtrie A, and its level l predecessor B, the depths of all the level l- 1  subtries of A are greater than the depths of A and B. In other words, the subtries of A form a C 0 -trie. A C 0 -trie data structure with this property is herein termed “well-formed”. (2) The values or strings in the index should be distinguished by the shortest possible prefixes. This is accomplished by having each value in the index should be valid or, in other words, there should be no unnecessary empty values or “dummies”. A C 0 -trie data structure with this property is herein said to be “taut”.  
         [0068]    [0068]FIG. 6 is a drawing depicting an illustrative instance of a C 0 -trie&#39;s selection vectors in accordance with an exemplary embodiment of the present invention. The selector parent  650  of selector vectors includes a level  1  selector vector  602  selecting all of the leaves of a represented C 0 -trie and is thus a bit vector the same length as a corresponding depth vector but consisting of all “1-bits”. A level  2  selector vector  604  selects level  2  subtries of leaves by having a 1-bit in the position corresponding the last element of a subtrie of level  1 . The subtries in each level are indexed by their position in the level. For example, a bit  606  set in second level selector vector selects a set of subtries  608  of level  1 . An index for this bit is shown as a “4”  609  beneath the bit. A level  3  selector vector  610  selects subtries of level  2  subtries in the same manner. For example, a bit  612  in the level  3  selector vector selects a level  2  subtrie  614 . This placement of level upon level may be repeated for as many levels as necessary to describe a C 0 -trie of arbitrary size as indicated by ellipses  616 . In this example, level  3  is the top level.  
         [0069]    Subtries may be selected by their index in a higher level subtrie. For example, a third subtrie  618  of a level  3  subtrie  614  is a level  2  subtrie  618  selected by set bit  620  at an index of “3”  622 . The level  2  subtrie  618  includes the level  1  subtries (leaves),  624  and  626 , at an index of “4”  628  and an index of “5”  622  respectively.  
         [0070]    A searching algorithm for a C 0 -trie as represented above exploits the properties of a well-formed and taut C 0 -trie. In a well-formed and taut subtrie, the depth of a subtrie is the depth of its last entry; that is, the depth corresponding to the set bit in a level l selector vector that designates the subtrie.  
         [0071]    [0071]FIG. 8 is a diagram depicting a value store data structure in accordance with an exemplary embodiment of the present invention. A value store structure  800  includes three parts: (1) a collection of storage pages  802  including the actual value or data that is to be stored; (2) a byte offset vector  806 ; and (3) a value identifier vector  810 .  
         [0072]    The storage pages  802  include the actual value or data that is to be stored. The number of storage pages is arbitrary as indicated by ellipses  804 . The storage pages are indexed by byte offset vector  806  wherein a nth offset is the position, in bytes, of the beginning of an nth string in the set of storage pages. The number of values in the byte offset vector is the same as the number of values stored in the set of storage pages as indicated by ellipses  808 . Value identifier vector  810  is a vector indexing the byte offset vector by lexical identifier (LID). The number of values in the value identifier vector is the same as in the byte offset vector as indicated by ellipses  812 . The LID is thus an index in lexicographical order of the values. For example, a string value that is 5 th  in lexicographical order corresponds to the LID  5 .  
         [0073]    [0073]FIG. 7 is a process flow diagram of a C 0 -trie search process in accordance with an exemplary embodiment of the present invention. The process starts ( 700 ) at a top level of the C 0 -trie, herein called the “top search level”. For ( 702 ) each subtrie in a next level beneath the top search level, herein termed the “top-1 search level”, the process searches ( 704 ) depths of the top-1 search level subtries. Only the depth values selected by the top-1 search level selector vector need to be examined because the C 0 -trie is well-formed as previously described. If the value is not identified ( 706 ) as being part of the current top-1 search level subtrie, the process continues ( 708 ) searching the remaining top-1 level subtries.  
         [0074]    When a top-1 search level subtrie including the searched for value is identified ( 706 ), the process descends ( 714 ) one level thus making the current top-1 search level the top search level and the identified top-1 search level subtrie an identified top search level subtrie. The process determines ( 716 ) if the new top search level is the previously described leaf selector level. If not, the process continues searching ( 718 ), and searches the top-1 search level subtries of the identified top search level subtrie. In this way, a search is limited to only one subtrie per search level.  
         [0075]    [0075]FIG. 9 is a process flow diagram of a deletion process in accordance with an exemplary embodiment of the present invention. A delete process deletes values from a C 0 -trie and rebuilds the C 0 -trie through a merging process in order to ensure the C 0 -trie remains well-formed. A delete process receives ( 900 ) a list of LIDs to delete. The delete process determines ( 902 ) if the empty string should be deleted. If the delete process determines ( 904 ) that a lot of LIDs are to be deleted in short segments, the delete process rebuilds ( 906 ) a new C 0 -trie using the remaining values in the old C 0 -trie. The threshold value for determining when a new C 0 -trie should be created rather than deleting values from and merging the remaining old C 0 -trie is application specific and depends on the relative speed of the delete process and the insert process.  
         [0076]    If only a small number of LIDs are to be deleted or a few big segments, then the delete process determines ( 908 ) if the C 0 -trie being operated on has only two levels. If there are only two levels, then leaves including the LIDs to be deleted may be readily deleted. However, if the C 0 -trie has more than two levels, then a branch delete process is called ( 912 ) to traverse the branch of the C 0 -trie including LIDs to be deleted and delete LIDs from that branch of the C 0 -trie.  
         [0077]    Once the LIDs have been deleted from the C 0 -trie, the delete process determines ( 914 ) if the remaining C 0 -trie has more than two remaining levels. If so, the delete process examines ( 916 ) the entire C 0 -trie and merges subtries where possible. Once the values have been deleted from the C 0 -trie and the C 0 -trie has been merged as needed, then the actual values are deleted ( 918 ) from the previously described data store.  
         [0078]    [0078]FIG. 10 is a process flow diagram of a C 0 -trie merge control process in accordance with an exemplary embodiment of the present invention. The merge control process determines ( 1000 ) if a large number of LIDs and a large number of runs of LIDs were deleted from the C 0 -trie being processed. If so, the merge control process discards ( 1002 ) the existing C 0 -trie except for the leaf level and then rebuilds the C 0 -trie&#39;s levels.  
         [0079]    If the merge control process determines that a small number of LIDs or a small number of runs of LIDs were deleted from the C 0 -trie being processed, the merge control process removes ( 1004 ) any duplicate levels in the C 0 -trie that may have been created during the deletion process. The merge control process starts ( 1006 ) at the top level of the C 0 -trie and traverses each changed subtrie down to a target level. Once the target level is reached, the merge control process calls a merge process that merges ( 1008 ) subtries as needed. The merge control process determines ( 1012 ) if any merges were actually performed on the target level by the merge process. If so, the merge control process deletes ( 1014 ) any duplicate levels that might have been created during the merge process.  
         [0080]    [0080]FIG. 11 is a process flow diagram of a C 0 -trie merge process as used in an exemplary embodiment of the present invention. The merge process is called by the previously described merge control process in order to traverse a subtrie to a target level and then merge subtries at the target level. A subtrie is a candidate for merging if it includes LIDs whose preceding neighbors have been deleted during the previously described deletion process, thus isolating an LID. An isolated LID is herein termed a “survivor” LID. The merge process receives as arguments a level l which is the current working level in the subtrie and a counter of the number of levels to go before the merge process can cease traversing the subtrie and merge isolated LIDs. The merge process determines ( 1100 ) if there are any LIDs following a run of deleted LIDs that are in level l of the subtrie. While there is at least one LID following a run of deleted LIDs, the merge process determines ( 1102 ) if it has traversed the subtrie down to the target level by checking the levels-to-go variable. If the merge process has more levels-to-go, the merge process determines ( 1104 ) the subtrie in the level below the current level l with the isolated LID, decrements ( 1106 ) the levels-to-go counter and recursively calls itself with a new level setting and the decremented levels to go counter. If the merge process determines ( 1102 ) that it has reached the target level by examining the levels-to-go counter, the merge process merges ( 1108 ) the subtrie including a survivor LID with the subtrie&#39;s preceding subtrie if possible. The merge process continues until all survivor LIDs have been processed ( 1110 ). Once all of the subtries on a target level have been processed, the target level is increased by one and processing continues.  
         [0081]    [0081]FIG. 12 is a process flow diagram of a branch delete process in accordance with an exemplary embodiment of the present invention. The branch delete process determines ( 1200 ) if there are LIDs that need to be deleted in a current level l subtrie for which branch delete was called. While there are LIDs to delete, the branch delete process identifies ( 1202 ) which subtrie in a level immediately below the current level include the LID. If the branch delete process determines ( 1204 ) that the identified subtrie can be deleted, such as when the identified subtrie includes only a single LID or a number of deleted LIDs in a row, the branch delete process deletes the entire subtrie and terminates without traversing the subtrie any further.  
         [0082]    If the identified subtrie cannot be deleted, the branch delete process determines ( 1208 ) if the level below the current level is the previously described level  2  of the C 0 -trie. If so, the branch delete process deletes the runs of leaves of the C 0 -trie as requested by the delete process. If not, the branch delete process recursively calls itself ( 1212 ) to continue processing the subtrie in the level immediately below the current level.  
         [0083]    [0083]FIG. 13 is a process flow diagram of an insertion process in accordance with an exemplary embodiment of the present invention. While ( 1300 ) the insertion process has values to insert into the C 0 -trie, the insert process determines ( 1302 ) if the C 0 -trie has only two levels. If so, the insertion process determines ( 1304 ) which existing leaf includes the key interval to which a value belongs. Once the existing leaf is identified, the insertion process inserts as many values as possible into the identified key interval. If the C 0 -trie has more than two levels, the insertion process calls a to-be-described branch insertion process  1308  to traverse the C 0 -trie and insert values into the C 0 -trie at the appropriate level. A subtrie is split when it no longer has the property of being well-formed because it now includes new values that have a depth less than or equal to the depth of the subtrie or the subtrie&#39;s predecessor in a particular level.  
         [0084]    After all of values have been inserted ( 1310 ) the insertion process determines ( 1312 ) if any new values have been inserted. If so, the insertion process determines if any of the subtries of the C 0 -trie should be split because the C 0 -trie has grown too large for efficient manipulation. The insertion process splits a subtrie by calling ( 1316 ) a to-be-described navigate-and-split function from the top level of the C 0 -trie. After the C 0 -trie has been processed ( 1318 ), the insertion process adds ( 1320 ) the new values to the actual value store.  
         [0085]    [0085]FIG. 14 is a process flow diagram of a branch insertion process in accordance with an exemplary embodiment of the present invention. While ( 1400 ) there are values to insert, the branch insertion process determines ( 1402 ) which level immediately below a current level includes the subtrie whose key interval includes the value&#39;s. If the branch insertion process determines ( 1404 ) the level immediately below the current level is not the level above the leaf level, the branch insertion process recursively calls itself for operation on the level immediately below the current level.  
         [0086]    If the branch insertion process determines ( 1404 ) the level immediately below the current level is the level above the leaf level, the branch insertion process determines ( 1408 ) which leaf key interval includes the inserted value&#39;s key and inserts ( 1410 ) as many values as possible into the key interval. The branch insertion process then checks ( 1411 ) if the next value is not in the current subtrie. If the next value is not in the current subtrie, the branch insertion process moves ( 1412 ) up the trie one level and determines ( 1414 ) if the C 0 -trie is still well-formed. If not, the branch insertion process performs a split ( 1416 ) on the subtrie into which the values were inserted. The branch insertion process continues until all values have been inserted ( 1417 ). Once the values have been inserted, the branch insertion process ends ( 1418 ).  
         [0087]    [0087]FIG. 15 is a process flow diagram of a C 0 -trie rebuilding process in accordance with an exemplary embodiment of the present invention. A C 0 -trie rebuilding process  1500  exploits the fact that the representations of the C 0 -tries are taut and well-formed. The C 0 -trie rebuilding process uses the previously described depth vectors and counter vectors to rebuild a C 0 -trie using the C 0 -trie&#39;s remaining subtries. Rebuilding a C 0 -trie is less time consuming than regenerating an entire C 0 -trie after a deletion process. During the rebuilding process, the previously described LIDs are used to keep track of elements within the trie; however, if the empty string is in the value store, the empty string is LID  1  but the empty string is not in the trie. Then the first element in the trie is LID  2 . The C 0 -trie rebuilding process sets ( 1502 ) a current survivor LID equal to a first survivor LID. While ( 1504 ) there are more surviving LIDs to process, the C 0 -trie rebuilding process gets ( 1504 ) the next survivor LID and determines ( 1508 ) if the next survivor LID is contiguous with a previous survivor LID and the current survivor LID. If this condition is met, then there are three surviving LIDS in a row and the depth of the current survivor LID and any dummy entries preceding it are the same as in the old depths. If so, the C 0 -trie rebuilding process copies ( 1510 ) the elements at the old depths located between position of the previous survivor LID and the position of the current survivor LID. This is possible because the depth of the previous survivor LID and the depth of the current survivor LID are unchanged and the positions of the depths in the old depths vector are unchanged.  
         [0088]    If the C 0 -trie rebuilding process determines that the next survivor LID is not contiguous with a previous survivor LID and the current survivor LID, the C 0 -trie rebuilding process starts at a level below the C 0 -trie&#39;s topmost level ( 1512 ) and determines if the current survivor LID and the next survivor LID are in the same level subtrie. If so, the C 0 -trie rebuilding process descends ( 1516 ) one more level into the C 0 -trie and makes the determination again. If the C 0 -trie rebuilding process determines that the current survivor LID and the next survivor LID are in not the same level subtrie, the C 0 -trie rebuilding process determines ( 1518 ) the depth of the current survivor LID as described in FIG. 16. The C 0 -trie rebuilding process then determines ( 1520 ) if the C 0 -trie needs new dummy entries at the depth of the current survivor LID. If so, the C 0 -trie rebuilding process puts ( 1522 ) any needed dummies in as described in FIG. 17. If no new dummy entries are needed, or after any needed dummies are created, the C 0 -trie rebuilding process goes ( 1524 ) up one level in the C 0 -trie and determines ( 1526 ) if the C 0 -trie rebuilding process is back at the top of the C 0 -trie. If so, the C 0 -trie rebuilding process continues processing by getting ( 1506 ) the next survivor LID. If not, the C 0 -trie process continues processing the C 0 -trie by moving up the C 0 -trie&#39;s levels and determining ( 1520 ) if the C 0 -trie needs new dummy entries at each level.  
         [0089]    [0089]FIG. 16 is a process flow diagram of a subtrie depth determination process as used by a C 0 -trie rebuilding process in accordance with an exemplary embodiment of the present invention. The C 0 -trie rebuilding process uses a subtrie depth determination process  1518  to determine the minimum depth of the subtries to which a LID belongs. The subtrie depth determination process does so by stepping through the previously described depths vector looking for the minimum depth of the subtries between the current survivor LID&#39;s subtrie and the next survivor LID&#39;s subtrie. The subtrie depth determination process sets ( 1600 ) a current minimum depth to a the depth of the current survivor LID&#39;s subtrie. The subtrie depth determination process then gets ( 1602 ) a subtrie to process and increments ( 1603 ) the selected subtrie. The subtrie depth determination process determines ( 1604 ) if the subtrie is the next survivor LID&#39;s subtrie. If so, the subtrie depth determination process sets ( 1608 ) the depth of the current survivor LID&#39;s subtrie to the current minimum value. Otherwise, the subtrie depth determination process determines ( 1610 ) if the depth of the subtrie is less than the current minimum depth. If so, the subtrie depth determination process sets the current minimum depth the depth of the subtrie. In either case, the subtrie depth determination process continues processing by getting ( 1602 ) another subtrie to process.  
         [0090]    [0090]FIG. 17 is a pseudocode listing of a dummy placement process in accordance with an exemplary embodiment of the present invention. If a dummy placement process  1522  determines ( 1700 ) that dummies may need to be placed in the current level of subtries, the dummy placement process sets ( 1701 ) a current minimum value at the last depth value in a temporary depth value vector (not shown) maintained to reconstruct the C 0 -trie. The temporary depth values vector includes depths needed for current LID in a new depths vector, and is filled in backwards from the way it will be put in the new depths vector created as the C 0 -trie is rebuilt. Therefore, the current minimum is the depth of either the current LID of FIG. 15 and FIG. 16 or the depth of the latest dummy put in the subtrie by the dummy placement process. The dummy placement process steps backwards in the subtries at this level, starting with the current LID&#39;s subtrie- 1  ( 1702 ). If the dummy placement process determines ( 1704 ) that the subtrie&#39;s position is greater than the previous position and determines ( 1706 ) the depth of the subtrie is less than the current minimum, the dummy placement process puts ( 1708 ) a dummy of subtrie&#39;s depth at the end of the temporary depth vector and sets ( 1710 ) the current minimum to the subtrie&#39;s depth. If the subtrie&#39;s position is not greater than the previous position, the dummy placement process stops ( 1712 ) processing the for loop.  
         [0091]    Although this invention has been described in certain specific embodiments, many additional modifications and variations would be apparent to those skilled in the art. It is therefore to be understood that this invention may be practiced otherwise than as specifically described. Thus, the present embodiments of the invention should be considered in all respects as illustrative and not restrictive, the scope of the invention to be determined by any claims supportable by this application and the claims&#39; equivalents.