US 6,553,370 B1 · Flexible search engine having sorted binary search tree for perfect match

Abstract

A binary search tree is structured so that keys or addresses associated with data in the bottom vertices are arranged in a predetermined order, such as ascending key address order. The root vertex and each hierarchy vertex contains the lowest value key from each child vertex and are thus similarly arranged by key value order. Each vertex of each level contains at least k and no more than 2k−1 keys, where k is an integer ≦2 and is constant for all vertices of a given level, but may vary between levels. The result is a structured tree having equal path lengths between the root vertex and each bottom vertex for search purposes. Keys are deleted and inserted to the bottom vertices by restructuring the tree under control of computer instructions.

Claims27

Dependent claims

A computer readable medium containing an expandable and/or contractible binary search tree for conducting a search for a key associated with data in a computer database, the search tree having a plurality of vertices arranged in a plurality of levels with a bottom level containing a plurality of bottom vertices each containing at least k, and no more than 2k−1, entries, where k is an integer ≧2, each entry in a bottom vertex associating a key with data, a top level containing a root vertex defining an input to the tree, and at least one intermediate level containing a plurality of hierarchy vertices defining at least a portion of a path between the root vertex and a bottom vertex, each hierarchy vertex containing at least k, and no more than 2k−1, entries, each entry in a hierarchy vertex comprising a key contained in a bottom vertex entry and a vertex address of a lower level vertex to define a portion of the path between the root vertex and the bottom vertex containing the key, the keys in each level being distributed through the vertices of the respective level in a predetermined order.

A process for altering a structured binary search tree in a computer of the class having a plurality of vertices arranged in a plurality of levels with a bottom level containing a plurality of bottom vertices each containing a plurality of keys and associated data, a top level containing a root vertex defining an input to the tree, and at least one intermediate level containing a plurality of hierarchy vertices defining at least a portion of a path between the root vertex and a bottom vertex, with each hierarchy vertex containing a plurality of entries comprising a key contained in a bottom vertex entry and a vertex address of a lower level vertex to define a portion of the path between the root vertex and the bottom vertex containing the key, the search tree being structured such that keys are distributed though the vertices of each level in a predetermined order, the process comprising steps of:

a) altering the number of keys in at least one bottom level vertex;
b) identifying the number of keys in the altered bottom level vertex, and either
c) if the identified number of keys is less than k, where k is an integer ≧2, adjusting the location of keys among the bottom vertices until all bottom vertices contain no less than k keys;
and
d) if the identified number of keys is greater than 2k−1, transferring a key from the adjusted bottom vertex to another bottom vertex until all bottom vertices contain no more than 2k−1 keys.

2 more elements

A computer usable medium having a computer readable program embodied therein for addressing data, the computer readable program in the computer usable medium comprising:

computer readable program code defining a search tree having a plurality of vertices arranged in a plurality of levels with a bottom level containing a plurality of bottom vertices each containing k to 2k−1 entries each associating a key, with data, where k is a predetermined integer ≧2, a top level containing a root vertex defining an input to the tree, and at least one intermediate level containing a plurality of hierarchy vertices defining at least a portion of a path between the root vertex and a bottom vertex, each hierarchy vertex containing k to 2k−1 entries comprising a key contained in a bottom vertex entry and a vertex address of a lower level vertex to define a portion of the path between the root vertex and the bottom vertex containing the key,
computer readable program code for causing a computer to insert keys into, and delete keys from, bottom vertices of the search tree, and
computer readable program code for causing a computer to reconstruct the hierarchy vertices so that that the keys are distributed through the vertices of each level in a predetermined order.

Dependencies are inferred from the claim text.

Flexible search engine having sorted binary search tree for perfect match

Life of this patent

Flexible search engine having sorted binary search tree for perfect match

Life of this patent

Abstract

Claims27