System and method for prediction of read commands to non-sequential data

A memory device comprising:

• a first memory;
• a second memory comprising:
• a search sequence buffer;
• and
• a prior read command data structure, the prior read command data structure having only a predetermined number of entries that are each indexed with a respective index value within a predetermined range of index values;
• and
• a controller in communication with the first memory and the second memory, the controller configured to:
• receive a current read command comprising read command data including a start logical block address (LBA) and a data length, where the start LBA of the current read command is discontiguous with an address range associated with a last read command received prior to the current read command;
• generate a search sequence in the search sequence buffer based on read command data from a plurality of prior read commands including at least the current read command and the last read command;
• calculate an index value, based on the search sequence, within the predetermined range of index values;
• retrieve, from an entry in the prior read command data structure indexed by the calculated index value, data representative of a historical next read command associated with the calculated index value;
• and
• pre-fetch data from the first memory to the second memory based on the retrieved data representative of the historical next read command.

A memory device comprising:

• a first memory;
• a second memory;
• means for updating a prior read command data structure of prior next read commands in the second memory by:
• calculating, from of a sequence of read commands preceding a current read command, one of a plurality of predetermined index values;
• and
• storing read command data for the current read command in an entry of the prior read command data structure indexed by the one of the plurality of predetermined index values;
• and
• means for predicting and pre-fetching data for a next read command by:
• calculating an index value of the plurality of predetermined index values from a search sequence of prior received read commands;
• and
• retrieving read command data from a historical next read command in an entry of the prior read command data structure indexed to the calculated index value.