Smart pre-fetch for sequential access on BTree

Patent metadata

Field	Value
Publication number	US-9552298-B2
Application number	US-201314142312-A
Country	US
Kind code	B2
Filing date	Dec 27, 2013
Priority date	Dec 27, 2013
Publication date	Jan 24, 2017
Grant date	Jan 24, 2017

Abstract

Methods and systems configured to facilitate smart pre-fetching for sequentially accessing tree structures such as balanced trees (b-trees) are described herein. According to various described embodiments, a pre-fetch condition can be determined to have been met for a first cache associated with a first level of a tree such as a b-tree. A link to a bock of data to be read into the cache can be read into the cache by accessing a second level of the tree. The data elements associated with the retrieved link can subsequently read into the cache.

First claim

What is claimed is:

1. A method, comprising:
determining, by a controller, that a pre-fetch condition has been met for a first cache associated with a first level of a balanced tree (b-tree);
retrieving a link to a memory for data element to be read into the cache by accessing a second level of the b-tree;
writing the data element associated with the retrieved link into the cache;
determining that a pre-fetch condition has been met for a second cache associated with the second level of the b-tree; and
pre-fetching data for the second cache.

2. The method of claim 1 , wherein a capacity of the first cache is bigger than a capacity of the second cache.

3. The method of claim 1 , wherein determining that the pre-fetch condition has been met for the first cache comprises determining that a read request has been made to the controller.

4. The method of claim 1 , wherein determining that the pre-fetch condition has been met for the first cache comprises determining that a pre-determined portion of a previously cached data element has already been accessed.

5. The method of claim 1 , wherein determining that the pre-fetch condition has been met for the first cache comprises determining that a first data element in the cache is going to be accessed by the next read action.

6. The method of claim 5 , further comprising removing the first data element from the cache.

7. The method of claim 1 , further comprising:
determining that an additional pre-fetch condition has been met for the first cache; and
pre-fetching an additional data element.

8. The method of claim 1 , wherein the first level of the b-tree is a child level of the second level of the b-tree.

9. The method of claim 1 , further comprising pre-fetching a number of additional data elements of data sufficient to fill the first cache.

10. A system, comprising:
a memory; and
a controller communicatively coupled to the memory and configured to:
determine that a pre-fetch condition has been met for a first cache associated with a first level of a balanced tree (b-tree);
retrieve a link to a data element to be read into the cache by accessing a second level of the b-tree;
write the data element of data associated with the retrieved link into the cache; and
determine that a pre-fetch condition has been met for a second cache associated with the second level of the b-tree; and
pre-fetch data for the second cache.

11. The system of claim 10 , wherein a capacity of the first cache is bigger than a capacity of the second cache.

12. The system of claim 10 , wherein the controller is configured to determine that the pre-fetch condition has been met for the first cache by determining that a read request has been made to the controller.

13. The system of claim 10 , wherein the controller is configured to determine that the pre-fetch condition has been met for the first cache by determining that a pre-determined portion of a previously cached data element has already been accessed.

14. The system of claim 10 , wherein the controller is configured to determine that the pre-fetch condition has been met for the first cache by determining that a first data element in the cache is going to be accessed by the next read action.

15. The system of claim 14 , wherein the controller is further configured to remove the first data element from the cache.

16. The system of claim 10 , wherein the controller is further configured to:
determine that an additional pre-fetch condition has been met for the first cache; and
pre-fetch an additional data element.

17. The system of claim 10 , wherein the first level of the b-tree is a child level of the second level of the b-tree.

18. The system of claim 10 , wherein the controller is further configured to pre-fetch a number of additional data elements of data sufficient to fill the first cache.

19. The method of claim 1 , further comprising:
determining whether a next data element is available at a current node;
retrieving a link to a memory for the next data element; and
writing the next data element to the cache.

20. The system of claim 10 , wherein the controller is further configured to:
determine whether a next data element is available at a current node;
retrieve a link to a memory for the next data element; and

write the next data element to the cache.

Assignees

• Mungikar Shailesh
• French Blaine
• Sybase Inc

Inventors

• Mungikar Shailesh
• French Blaine

Classifications

• G06F12/0871

  Allocation or management of cache space · CPC title

• G06F2212/466

  Metadata, control data · CPC title

• G06F2212/1024

  Latency reduction · CPC title

• G06F2212/6028

  Prefetching based on hints or prefetch instructions · CPC title

• G06F2212/602

  Details relating to cache prefetching · CPC title