A method and apparatus for increasing the speed of a search through leaf nodes of an inventive key index tree structure, known as a "Q-tree". The present invention identifies "decision-bits" within leaf node entries and uses these decision-bits to accelerate searches for a particular record or for a record adjacent to which a new record is to be inserted. A decision-bit is a particular type of distinction-bit having the smallest value and associated with a search key a greater value then the keys associated with other distinction-bits of the same value within a specified search range. Each decision-bit divides a search range into "left" and "right" parts. One of the two parts will constitute a "new" search range. A "quit-bit" having an ordinal number equal to the value of the decision-bit for the search range, is tested. If the quit-bit is "on", then the right, or greater value, part becomes the new search range. Otherwise, the left, or lesser value, part becomes the new search range. A decision-bit pointer which identifies the relative location of a "root" decision-bit is placed in a predetermined location within the prologue of each leaf node. Additional decision-bit pointers are associated with each subsequent decision-bit within the leaf node and indicate the relative location of such decision-bits with respect to the root decision-bit.
A search key having a first length is presented to a universal hashing process. The search key is hashed using a universal hash function to generate a bucket ID having a second length, smaller than the first length. The bucket ID is used to address a table stored in a computer readable medium and a pointer is retrieved from an associated storage location. The pointer is used to index a hash bucket containing one or more entries, each of which can be compared to the search key to determine whether any of the entries match the search key. For the case where the method is used in a Ethernet switch, the search key may comprise a virtual LAN identification and media access control address. The table is made up of number of hash buckets, each of which may have one or more entries. New entries are stored in one of the hash buckets according to the universal hash function so long as no overflows of any hash bucket would be created. If a bucket overflow would result from the storing operation, a new hash function is automatically selected so that no hash bucket overflows will result when the new entry is stored in a new table.
In order to search a file to be searched which includes records having fields allocated to each of a plurality of hierarchical levels and is constructed so that records having a same key character string in a field at a same hierarchical level are arranged in series, an index file is created by obtaining start position information and number information about records having a key character string contained in the hierarchical level of each node on the file to be searched, or a pointer to node management information of a lower hierarchical level, and by recording the information obtained for the nodes of all the hierarchical levels. Further, data is extracted from the file to be searched by using the record start position information, the record number information, and the pointer to the node management information of a lower hierarchical level recorded in the index file.
A device for parallel processing of subtrees within a binary tree for searching for the tree leaf matching a search key. The search is performed at each node by applying a recursive function associated with each node and whose parameters depend on the node for determining which branch, left or right, is to be taken in accordance with the search key. The device includes subtree register blocks for storing the recursive functions, processors for processing the recursive functions, a control unit that assigns one processor to the processing of the recursive functions contained in a block that sent the request to the control unit, and means for selecting subtrees included in the sequence of branches between the root and the leaf defined in accordance with the search key in response to the processing of blocks.
The invention herein provides method and apparatus for managing attribute-tagged index entries contained in an index by assigning or tagging an index entry attribute indicator to a newly inserted index entry (that is, at the time when a key data value is inserted into the index, the key data value becomes a newly inserted index entry and an attribute indicator is tagged to the newly inserted index entry). The index entry can be placed anywhere within the index. Once a group of attribute-tagged index entries have been inserted into the index, the attribute identifiers can be switched off instantaneously (that is, the attribute associated with the attribute indicators is disabled).
Cache sensitive search tree (CSS-tree) index structures for providing improved search and lookup performance compared with conventional searching schemes. The CSS-tree index structures include a directory tree structure which is stored in an array (216) and serves as an index for a sorted array of elements. The nodes (215) in the directory tree structure may be of sizes selected to correspond to the cache line size in the computer system utilizing the CSS-tree index structures. Child nodes (213) within the directory tree structure are located by performing arithmetic operations on array offsets. Thus, it is not necessary to store internal child node pointers, thereby reducing memory storage requirements. In addition, the CSS-tree index structures are organized so that traversing each level in the tree yields good data reference locality, and therefore relatively few cache misses. Thus, the CSS-tree index structures consider cache-related parameters such as reference locality and cache behavior, without requiring substantial additional amounts of memory.
