Trie search engine
A method of searching a database that includes executing a trie search algorithm on a first portion of data in the database, returning a tag narrowing a location of the first portion of data to optimize the database, and performing a directed search of the optimized database by executing the trie search algorithm again on the optimized database, where the trie search algorithm is an information retrieval data structure using a M-ary tree where each node consists of a M-positional vector of pointers.
1. A method of accessing data from in a data storage device, comprising:
receiving, from a host device, an access request directed at a logical block address comprising a plurality of nibbles;
selecting a first nibble of the plurality of nibbles of the logical block address;
matching the first nibble of the plurality of nibbles of the logical block address through a first page of a trie mapping to an identified region of a flash translation layer without selecting all of the plurality of nibbles of the logical block address; and
searching, based on a result of the matching, the identified region of the flash translation layer without searching all individual entries of the flash translation layer.
2. The method of claim 1 , further comprising, prior to selecting the first nibble:
selecting a second nibble of the plurality of nibbles of the logical block address; and
matching the second nibble of the plurality of nibbles of the logical block address through a second page of the trie mapping to the first page of the trie mapping.
3. A data storage device, comprising:
a memory device configured to store:
a first flash translation layer, wherein the first flash translation layer includes a data address translation table; and
a first page of a trie mapping to an identified logical block address (LBA) region of LBA regions of the first flash translation layer;
a non-volatile memory array comprising one or more flash memory devices; and
a controller coupled to the memory device and coupled to the non-volatile memory array, the controller comprising one or more processors operable to:
receive an access request of a (LBA) comprising a plurality of nibbles;
select a first nibble of the LBA to be compared to the first page of the trie mapping;
match the first nibble of the LBA through the first page of the trie mapping to the identified LBA region of the first translation layer without selecting all of the plurality of nibbles of the LBA; and
search, based on a result of the first nibble matched to the identified LBA region, on the identified LBA region of the first flash translation layer without searching all of the LBA regions of the first flash translation layer.
4. The device of claim 3 , wherein the memory device contains a second flash translation layer.
5. The device of claim 3 , wherein the first flash translation layer includes data entries of logical block addresses and a corresponding physical data address.
6. The device of claim 3 , wherein the first flash translation layer includes an index that encodes logical block addresses of each entry.
7. The device of claim 3 , wherein the controller is further configured to consolidate multiple logical block addresses into a logical block address container, wherein the controller is further configured to fully specify a physical data address corresponding to the logical block address.
8. The device of claim 3 , wherein the controller is further configured to, prior to selecting the first nibble:
select a second nibble of the LBA;
match the second nibble of the LBA through a second page of the trie mapping to the first page of the trie mapping.