Data storage and retrieval system and method for storing cell coordinates in a computer memory
In an embodiment, a data storage and retrieval system includes a computing device that configures the computer memory according to an RTree (a type of logic tree) representing a structure of a spreadsheet. The computer memory may be internal to or external to the computing device. In an embodiment, the RTree has a plurality of nodes, at least some of which contain one or more minimum bounding rectangles. Each minimum bounding rectangle (“MBR”) encompasses cells of the spreadsheet from a different one of a plurality of columns of the spreadsheet, but does not encompass cells of any of the other columns of the plurality of columns. A node of the RTree may hold multiple MBRs or a single MBR.
1. A method for maintaining coordinates of cells of a spreadsheet, the method carried out by a first computing device communicatively linked to a second computing device, the method comprising:
representing the structure of the spreadsheet as an RTree comprising a plurality of nodes, in which
at least some of the plurality of nodes contain references to a cell of the spreadsheet, and
at least some of the plurality of nodes contains one or more minimum bounding rectangles, in which each minimum bounding rectangle represents a single column of the spreadsheet;
receiving a request for a search for a cell in the spreadsheet to be carried out;
in response to the request, carrying out a traversal of an RTree;
based on the traversal, identifying a node of the plurality containing the minimum bounding rectangle representing the column in which the cell is located,
loading, from a data store, one or more child nodes of the identified node until a node containing a reference to the cell is located;
retrieving contents of the cell using the reference;
carrying out a spreadsheet operation using the retrieved contents; and
updating the spreadsheet displayed on the second computing device in accordance with the spreadsheet operation.
2. The method of claim 1 , wherein the identified node contains a plurality of minimum bounding rectangles.
3. The method of claim 1 , wherein the first computing device recursively checks the plurality of nodes to determine whether the cell is located within a minimum bounding within the plurality of nodes.
4. The method of claim 1 , wherein the reference is a reference to a data structure in the data store.
5. A first computing device communicatively linked to a second computing device, the first computing device comprising processor hardware configured to carry out actions comprising:
representing the structure of the spreadsheet as an RTree comprising a plurality of nodes, in which
at least some of the plurality of nodes contain references to a cell of the spreadsheet, and
at least some of the plurality of nodes contains one or more minimum bounding rectangles, in which each minimum bounding rectangle represents a single column of the spreadsheet;
receiving a request for a search for a cell in the spreadsheet to be carried out;
in response to the request, carrying out a traversal of an RTree;
based on the traversal, identifying a node of the plurality containing the minimum bounding rectangle representing the column in which the cell is located,
loading, from a data store, one or more child nodes of the identified node until a node containing a reference to the cell is located;
retrieving contents of the cell using the reference;
carrying out a spreadsheet operation using the retrieved contents; and
updating the spreadsheet displayed on the second computing device in accordance with the spreadsheet operation.
6. The computing device of claim 5 , wherein the identified node contains a plurality of minimum bounding rectangles.
7. The computing device of claim 5 , wherein the first computing device recursively checks the plurality of nodes to determine whether the cell is located within a minimum bounding within the plurality of nodes.
8. The computing device of claim 5 , wherein the reference is a reference to a data structure in the data store.
9. A non-transitory computer-readable medium having stored thereon computer-executable instructions for carrying out actions comprising:
receiving a request for an action to be carried out on a cell of the spreadsheet;
in response to the request, carrying out a traversal of an RTree comprising a plurality of nodes, in which at least some of the plurality of nodes contains one or more minimum bounding rectangles, in which each minimum bounding rectangle represents a single column of the spreadsheet;
based on the traversal, identifying a node of the plurality containing the minimum bounding rectangle representing the column in which the cell is located,
loading, from a data store, one or more child nodes of the identified node until a node containing a reference to the cell is located;
retrieving contents of the cell using the reference;
carrying out a spreadsheet operation using the retrieved contents; and
updating the spreadsheet displayed on the second computing device in accordance with the spreadsheet operation.
10. The computer-readable medium of claim 9 , wherein the identified node contains a plurality of minimum bounding rectangles.
11. The computer-readable medium of claim 9 , wherein the first computing device recursively checks the plurality of nodes to determine whether the cell is located within a minimum bounding within the plurality of nodes.
12. The computer-readable medium of claim 9 , wherein the reference is a reference to a data structure in the data store.