Integrated search engine devices that support database key dumping and methods of operating same
View Patent ↗Methods of operating a search engine device include repeatedly reading next keys (and associated handles) from a database within the search engine device in order to identify and transfer some or possibly all of the contents of the database to another device (e.g., command host) requesting the database contents. An operation to read a next key includes: (i) searching a pipelined database within the search engine device with a first key to identify at least one key therein that is greater than the first key and then (ii) executing a next key fetch operation in the pipelined database to identify the next key from the at least one key. The next key and a handle associated with the next key are then retrieved from the search engine device (e.g., transferred to a command host).
1. A method of operating a search engine device, comprising:
reading a next key from the search engine device by:
searching a pipelined database within the search engine device with a first key to identify at least one key therein that is greater than the first key;
executing a next key fetch operation in the pipelined database to identify the next key from the at least one key; and then
retrieving the next key and a handle associated with the next key from the search engine device,
wherein the pipelined database comprises multiple levels of hierarchical processing logic, wherein each level of the multiple levels of hierarchical processing logic include (a) control and search logic, (b) storage for data structures for a level of a b-tree associated therewith, and (c) a node maintenance sub-engine, and
wherein searching a pipelined database within the search engine device comprises replacing an idle cycle detected at a highest level of the pipelined database with a next key search operation.
2. The method of claim 1 , wherein searching a pipelined database within the search engine device comprises searching the pipelined database within the search engine device with a first key to identify a respective next key candidate that is greater than the first key at each of a plurality of levels of the pipelined database; and wherein executing a next key fetch operation comprises identifying the next key as the next key candidate located at a lowest level of the pipelined database containing a next key candidate.
3. The method of claim 1 , wherein executing a next key fetch operation comprises replacing an idle cycle detected a highest level of the pipelined database with the next key fetch operation.
4. The method of claim 1 , wherein executing a next key fetch operation comprises replacing an idle cycle detected a highest level of the pipelined database with the next key fetch operation.
5. The method of claim 1 , wherein executing the next key fetch operation is preceded by generating a ready message that passes from a second level of the pipelined database to an immediately next higher first level of the pipelined database in response to storing a next key candidate at the second level of the pipelined database.
6. The method of claim 5 , wherein executing the next key fetch operation comprises passing a first next key candidate from the first level of the pipelined database to the second level of the pipelined database.
7. The method of claim 6 , wherein executing the next key fetch operation comprises passing a second next key candidate stored at the second level of the pipelined database from the second level of the pipelined database to an immediately next lower third level of the pipelined database.
8. The method of claim 1 , wherein executing the next key fetch operation is preceded by generating a ready message that passes from a second level of the pipelined database to an immediately next higher first level of the pipelined database.
9. The method of claim 8 , wherein executing the next key fetch operation comprises passing a first next key candidate from the first level of the pipelined database to the second level of the pipelined database.
10. The method of claim 9 , wherein executing the next key fetch operation comprises passing the first next key candidate from the second level of the pipelined database to an immediately next lower third level of the pipelined database; and wherein retrieving the next key comprises retrieving the first next key candidate and handle associated with the first next key candidate from the search engine device.
11. An integrated search engine device, comprising:
a storage device including a pipelined database for storing a plurality of search keys; and
a search engine configured to perform the steps of:
(a) search the pipelined database with a first key to identify at least one key therein that is greater than the first key,
(b) execute a next key fetch operation in the pipelined database to identify a next key from the at least one key, and
(c) output the next key and a handle associated with the next key,
wherein the pipelined database comprises multiple levels of hierarchical processing logic, wherein each level of the multiple levels of hierarchical processing logic include (a) control and search logic, (b) storage for data structures for a level of a b-tree associated therewith, and (c) a node maintenance sub-engine, and
wherein searching a pipelined database within the search engine device comprises replacing an idle cycle detected at a highest level of the pipelined database with a next key search operation.
12. The integrated search engine device of claim 11 , wherein the search engine is further configured to search the database with a first key to identify a respective next key candidate that is greater than the first key at each of a plurality of levels of the database, and wherein the next key corresponds to the next key candidate located at a lowest level of the database containing a next key candidate.
13. An integrated search engine device, comprising:
a hierarchical memory configured to store a plurality of databases of search keys therein arranged as a corresponding plurality of multi-way trees that span multiple levels of the hierarchical memory; and
a plurality of search and tree maintenance sub-engines for dumping keys from a first one of the plurality of databases to a second one of the plurality of databases, the plurality of search and tree maintenance sub-engines being configured to:
search the first one of the plurality of databases for a first key stored therein to obtain a handle associated with the first key;
store the first key and the handle associated with the first key in the second one of the plurality of databases;
search the first one of the plurality of databases using the first key identified therein as a search key to obtain a second key and a handle associated with the second key; and
store the second key and the handle associated with the second key in the second one of the plurality of databases,
wherein the plurality of search and tree maintenance sub-engines comprises multiple levels of hierarchical processing logic, wherein each level of the multiple levels of hierarchical processing logic include (a) control and search logic, (b) storage for data structures for a level of a b-tree associated therewith, and (c) a node maintenance sub-engine, and
wherein searching the hierarchical memory within the search engine device comprises replacing an idle cycle with a search operation.