Using a B-tree to store graph information in a database
Techniques to store graph information in a database are disclosed. In various embodiments, each node in a graph may be modeled as a micro b-tree. Node identity, attribute, edge, and edge attribute data may be stored in one or more pages modeled on page formats typically used to store index data for a relational database index. Data associated with a plurality of nodes and edges, each of said edges representing a relationship between two or more of said nodes, may be received. For each node, one or more pages of data may be created, each corresponding to a prescribed page size associated with a storage device in which said one or more pages are to be stored, and each page having a data structure that includes a variable-sized set of fixed length data slots and a variable-sized variable length data region.
1. A system, comprising:
a storage device organized as a plurality of pages of a prescribed page size; and
a processor coupled to the storage device and configured to:
receive data associated with a plurality of nodes and edges, each of said edges representing a relationship between two or more of said nodes;
create for each node one or more pages of data, each corresponding to said prescribed page size, and each page having a b-tree index data structure that includes a first section having a variable-sized set of fixed width data slots and a second section having a variable-sized variable length data region;
perform at least one of a read, update, and delete transaction operation on the plurality of nodes and edges; and
determine traversal of relationships between nodes and edges;
wherein each data slot includes a slot header and a slot data region;
wherein the slot header includes values to indicate slot type, slot status, and edge direction;
wherein the slot data region stores one of edge slot data values and attribute slot data values.
2. The system of claim 1 , wherein said fixed length data slots are configured to be used to store one or more of node attribute data, edge data, and edge attribute data associated with the node.
3. The system of claim 1 , wherein data values too large to be stored in said fixed length data slots is stored.
4. The system of claim 1 , wherein the slot header includes one or more fields to store the slot type.
5. The system of claim 4 , wherein the slot type indicates a type of data stored in or stored in a location identified by data stored in a corresponding slot data value section of that slot.
6. The system of claim 5 , wherein the slot data value section is configured to store a primitive value of a size equal to or smaller than a fixed width of said slot data value section.
7. The system of claim 1 , wherein the slot header includes a field to store an offset indicating a location in which a corresponding value is located within said variable length data region.
8. The system of claim 1 , wherein said processor is configured to add slots to said page and increase a size of said variable length data region as needed to store additional data associated with a given node until there is no further available space in said page of said prescribed page size.
9. The system of claim 8 , wherein the processor is configured to split the page if additional data is to be stored for a node and would result in a page that exceeds said prescribed page size.
10. The system of claim 1 , wherein the processor is further configured to sort said data slots prior to writing said page to the storage device.
11. The system of claim 10 , wherein the processor is configured to sort the slots based at least in part on a respective slot type of each slot.
12. The system of claim 10 , wherein the processor is configured to sort the slots in a manner that results in node attributes being included first in sorted order, followed by edges owned by the node, followed by edge attributes.
13. A method, comprising:
receiving data associated with a plurality of nodes and edges, each of said edges representing a relationship between two or more of said nodes;
creating for each node one or more pages of data, each corresponding to a prescribed page size associated with a storage device in which said one or more pages are to be stored, and each page having a b-tree index data structure that includes a first section having a variable-sized set of fixed width data slots and a second section having a variable-sized variable length data region;
performing at least one of a read, update, and delete transaction operation on the plurality of nodes and edges; and
determining traversal of relationships between nodes and edges;
wherein each data slot includes a slot header and a slot data region;
wherein the slot header includes values to indicate slot type, slot status, and edge direction;
wherein the slot data region stores one of edge slot data values and attribute slot data values.
14. The method of claim 13 , wherein said fixed length data slots are configured to be used to store one or more of node attribute data, edge data, and edge attribute data associated with the node.
15. The method of claim 13 , wherein data values too large to be stored in said fixed length data slots is stored.
16. The method of claim 13 , wherein the slot header includes one or more fields to store the slot type.
17. The method of claim 16 , wherein the slot type indicates a type of data stored in or stored in a location identified by data stored in a corresponding slot data value section of that slot.
18. A computer program product embodied in a non-transitory computer readable medium and comprising computer instructions for:
receiving data associated with a plurality of nodes and edges, each of said edges representing a relationship between two or more of said nodes;
creating for each node one or more pages of data, each corresponding to a prescribed page size associated with a storage device in which said one or more pages are to be stored, and each page having a b-tree index data structure that includes a first section having a variable-sized set of fixed width data slots and a second section having a variable-sized variable length data region;
performing at least one of a read, update, and delete transaction operation on the plurality of nodes and edges; and
determining traversal of relationships between nodes and edges;
wherein each data slot includes a slot header and a slot data region;
wherein the slot header includes values to indicate slot type, slot status, and edge direction;
wherein the slot data region stores one of edge slot data values and attribute slot data values.