Data storage and retrieval system and method for storing cell coordinates in a computer memory

1. A data storage and retrieval 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,

wherein the RTree is configured according to a map,

wherein the RTree comprises a plurality of nodes, at least some of which contain one or more minimum bounding rectangles, each minimum bounding rectangle encompassing coordinates of one or more cells of the spreadsheet,

wherein the spreadsheet comprises a first row and a second row,

wherein the map comprises

a mapping between a coordinate of the first row as displayed and a coordinate of a first node of the RTree, and

a mapping between a coordinate of the second row as displayed and a coordinate of a second node of the RTree,

the first computing device configured to carry out steps comprising

retrieving the plurality of nodes from the data store;

in response to a row being inserted between the first row and the second row of the spreadsheet as displayed, and without retrieving further nodes from the data store, updating the map to include a mapping between the inserted row and a fractional coordinate that is between the coordinate of the first node and the coordinate of the second node and leaving the RTree unchanged; and

in response to a row of the spreadsheet being deleted, updating and re-inserting nodes with ranges containing start or stop rows corresponding to the deleted row.

2. The data storage and retrieval system of claim 1 , wherein the fractional coordinate is the lexical midpoint between the coordinate of the first row and the coordinate of the second row.

3. The data storage and retrieval system of claim 1 , wherein the plurality of nodes of the RTree are ordered based on the ranges encompassed by the plurality of minimum bounding rectangles.

4. A method of storing and retrieving data, the method carried out on a first computing device that is communicatively linked to a second computing device that displays a spreadsheet that includes a plurality of occupied cells and to an external data store, the method comprising:

the first computing device

maintaining nodes of an RTree, wherein the nodes contain minimum bounding rectangles of the plurality of occupied cells;

mapping display coordinates of the plurality of occupied cells to coordinates of the nodes;

retrieving the plurality of nodes from the data store;

in response to a row being inserted into the spreadsheet between adjacent rows of the spreadsheet as displayed, and without retrieving further nodes from the data store, updating the mapping to include a fractional coordinate of one of the nodes, which contains a minimum bounding rectangle for the inserted row, and leaving the RTree unchanged; and

in response to a row of the spreadsheet being deleted, updating and re-inserting nodes with ranges containing start or stop rows corresponding to the deleted row,

wherein the fractional coordinate is between coordinates of nodes containing minimum bounding rectangles for the adjacent rows.

5. The method of claim 4 , further comprising the second computing device:

visually displaying the spreadsheet on a display device;

maintaining the display coordinates of the occupied cells;

maintaining references to values or formulas contained in the occupied cells; and

receiving a user input indicating the insertion of the row.

6. The method of claim 4 , further comprising: in response to the row being deleted from the spreadsheet, deleting one of the maintained nodes, wherein the deleted node includes a minimum bounding rectangle for the deleted row.

7. A method for storing data to and retrieving data from a computer memory, the method carried out by a first computing device and comprising:

configuring the computer memory according to an RTree representing a structure of a spreadsheet displayed on a second computing device;

configuring the RTree according to a map,

wherein the RTree comprises a plurality of nodes, at least some of which contain one or more minimum bounding rectangles, each minimum bounding rectangle encompassing coordinates of one or more cells of the spreadsheet,

wherein the spreadsheet comprises a first row and a second row,

mapping a coordinate of the first row as displayed to a coordinate of a first node of the RTree;

mapping a coordinate of the second row as displayed to a coordinate of a second node of the RTree;

retrieving the plurality of nodes from the data store;

in response to a row being inserted between the first row and the second row of the spreadsheet as displayed, and without retrieving further nodes from the data store, updating the map to include a mapping between the inserted row to a fractional coordinate that is between the coordinate of the first node and the coordinate of the second node and leaving the RTree unchanged; and

in response to a row of the spreadsheet being deleted, updating and re-inserting nodes with ranges containing start or stop rows corresponding to the deleted row.

8. The method of claim 7 , wherein the fractional coordinate is the lexical midpoint between the coordinate of the first row and the coordinate of the second row.

9. The method of claim 7 , wherein the plurality of nodes of the RTree are ordered based on the ranges encompassed by the plurality of minimum bounding rectangles.