Systems and methods for storing and accessing data stored in a data array
View Patent ↗Methods, systems, and apparatus for storing and accessing data stored in a data array are presented. In one embodiment, data is stored in a data array that includes a plurality of nodes. The nodes of the data array are segmented into one or more standard and priority pages. The pages are represented in a packed index. The priority pages are then cached and the standard pages are saved to disk. In another embodiment, data stored in a node of a data array may be accessed wherein the data array is segmented into at least one priority page and at least one standard page and the data array includes a plurality of nodes. A request for data stored in the node may be received. A priority page and/or a standard page may be searched for the node and, when found, the node may be accessed.
1. A method of storing data in a data array, wherein the data array includes a plurality of nodes, the method comprising:
segmenting the nodes of the data array into one or more standard and priority pages, wherein a priority page includes priority data;
representing the one or more standard and priority pages in a packed index, wherein a first bit of the packed index information for a page is allocated to indicate that the page is a priority page;
caching the one or more priority pages; and
saving the one or more standard pages to a disk.
2. The method of claim 1 , further comprising:
determining whether a node includes priority data;
transferring the node into a priority page based on the determination; and
updating the packed index to show that the node is in the priority page.
3. The method of claim 1 , wherein the data stored is log data.
4. The method of claim 1 , wherein the one or more standard or priority pages are of a regular and consistent type and are small in size.
5. The method of claim 1 , wherein a node is stored on only one page of the data array.
6. The method of claim 1 , wherein the data array is an AVL tree.
7. The method of claim 1 , further comprising:
allocating a top portion of the packed index information for a page to represent the page number of the page in the array; and
allocating a bottom portion of the packed index information for the page to represent an immediate index within the page.
8. The method of claim 1 , further comprising:
including the nodes in a top portion of the data array in a priority page.
9. The method of claim 1 , wherein the data array includes a plurality of priority pages.
10. The method of claim 1 , further comprising:
representing, with a first priority page, a first set of layers of the data array;
representing, with a second priority page, a second set of layers of the data array; and
representing, with a third and fourth priority page, a third set of layers of the data array.
11. The method of claim 1 , further comprising:
periodically determining whether the data in a node located in a priority page is still priority data;
transferring the node from the priority page to a standard page, based upon a determination that the data is not priority data; and
updating the packed index to show that the node is in a standard page.
12. The method of claim 1 , further comprising:
periodically determining whether the data in a node located in a standard page is priority data;
transferring the node from the standard page to a priority page, based upon a determination that the data is priority data; and
updating the packed index to show that the node is in a priority page.
13. The method of claim 1 , wherein the data node is a new or existing node.
14. A system for storing data in a data array, wherein the data array includes a plurality of nodes, the system comprising:
a data storage system for segmenting the nodes of the data array into one or more standard and priority pages, wherein a priority page includes priority data;
a packed index for representing the one or more standard and priority pages, wherein a first bit of the packed index information for a page is allocated to indicate that the page is a priority page;
a cache for caching the one or more priority pages; and
a disk for saving the one or more standard pages.
15. An apparatus for storing data in a data array, wherein the data array includes a plurality of nodes, the apparatus comprising:
a data storage system for segmenting the nodes of the data array into one or more standard and priority pages, wherein a priority page includes priority data;
a packed index for representing the one or more standard and priority pages, wherein a first bit of the packed index information for a page is allocated to indicate that the page is a priority page;
a cache for caching the one or more priority pages; and
a disk for saving the one or more standard pages.