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 data storage and retrieval system for a computer memory, the system comprising:
a first computing device communicatively linked to a second computing device and to an external data store,
the first computing device comprising a memory having stored thereon an RTree representing a structure of a spreadsheet displayed on the second computing device, the RTree comprising a plurality of nodes, including a first node containing one or more minimum bounding rectangles and a second node containing one or more minimum bounding rectangles in which each minimum bounding rectangle represents a single column of the spreadsheet, such that each minimum bounding rectangle
encompasses cells of the spreadsheet from a different one of a plurality of columns of the spreadsheet, and
does not encompass cells of any of the other columns of the plurality of columns,
the first computing device configured to carry out steps comprising
receiving a request for an action to be carried out on a cell of the spreadsheet;
traversing the RTree in response to the request;
based on a determination that the first node does not contain the minimum bounding rectangle representing the column in which the cell is located, refraining from retrieving any child nodes of the first node from the data store;
based on a determination that the second node contains the minimum bounding rectangle representing the column in which the cell is located, loading one or more child nodes of the second node from the data store until a node containing a reference to the cell is located;
carrying out the requested action with respect to the cell;
updating the spreadsheet displayed on the second computing device in accordance with the carried out action.
2. The data storage and retrieval system of claim 1 , wherein one or more of the first and second nodes contains a plurality of minimum bounding rectangles.
3. The data storage and retrieval system of claim 1 , wherein
the request is for a summation on the cell.
4. The data storage and retrieval system 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 rectangle contained in the plurality of nodes.
5. The data storage and retrieval system of claim 4 , wherein the reference is a reference to a data structure in the data store.
6. A method for maintaining coordinates of cells of a spreadsheet in a computer memory, the method carried out by a first computing device communicatively linked to a second computing device and to an external data store, the first computing device comprising a memory having stored thereon an RTree representing a structure of a spreadsheet displayed on the second computing device, the RTree comprising a plurality of nodes, including a first node containing one or more minimum bounding rectangles and a second node containing one or more minimum bounding rectangles, in which each minimum bounding rectangle represents a single column of the spreadsheet, such that each minimum bounding rectangle
encompasses cells of the spreadsheet from a different one of a plurality of columns of the spreadsheet, and
does not encompass cells of any of the other columns of the plurality of columns,
the method comprising
receiving a request for an action to be carried out on a cell of the spreadsheet;
traversing the RTree in response to the request;
based on a determination that the first node does not contain the minimum bounding rectangle representing the column in which the cell is located, refraining from retrieving any child nodes of the first node from the data store;
based on a determination that the second node contains the minimum bounding rectangle representing the column in which the cell is located, loading one or more child nodes of the second node from the data store until a node containing a reference to the cell is located;
carrying out the requested action with respect to the cell;
updating the spreadsheet displayed on the second computing device in accordance with the carried out action.
7. The method of claim 6 , wherein one or more of the first and second nodes contains a plurality of minimum bounding rectangles.
8. The method of claim 6 , wherein the request is a request for a search for the cell in the spreadsheet.
9. The method of claim 6 , wherein the first computing device recursively checks the plurality of nodes to determine whether the cell is located within a minimum bounding rectangle within the plurality of nodes.
10. The method of claim 6 , wherein the reference is a reference to a data structure in the data store.