Regressable differential data structures
A proposed modification to a record of a base data structure is identified, the records of the base data structure sorted by primary key. A type of modification of the proposed modification is identified. A record is added to a differential data structure of the type, the differential data structure record describing the proposed modification. A record is added to a delta data structure sorted by the primary key, the delta data structure record including the primary key value of the record, the type of the proposed modification, and a pointer to the record added to the differential data structure. Data can be fetched using the delta data structure to apply modifications to a set of records requested in the fetch and generate a modified set of records to be returned in a response to the request.
1. A system comprising:
at least one processor; and
memory including instructions that, when executed by the at least one processor; cause the at least one processor to perform operations to:
identify a proposed modification to at least one record of a base data structure including a plurality of records and sorted by primary key of the plurality of records;
identify that a differential data structure corresponds to a type of modification;
add a first record to the differential data structure including a row within the differential data structure and describes the proposed modification;
add a second record to a delta data structure sorted by the primary key that includes a primary key value of the second record, the type of the proposed modification, and a row number of the first record within the differential data structure;
incorporate, upon approval of the proposed modification, the proposed modification into a data model using the base data structure, the differential data structure, and the delta data structure; and
delete, upon expiration of a period of time provided for approval of the proposed modification via the data model without approval of the proposed modification, both the first record from the differential data structure and the second record from the delta data structure.
2. The system of claim 1 , the memory further comprising instructions that cause the at least one processor to store a copy of the delta data structure and the differential data structure with version data that includes a version of an updated base data structure updated using the delta data structure, wherein the version data is incorporated with the proposed modification into the data model.
3. The system of claim 1 , wherein the type of modification is one of a set including insertion of a new record, updating a value of an existing record, and deleting an existing record; and
the differential data structure includes at least one delete table, at east one update table, and at least one insert table.
4. The system of claim 3 , wherein the base data structure includes a plurality of columns and the at least one update table that comprises a plurality of separate update tables, each update table in the plurality of update tables corresponding to respective updates to a respective one of the plurality of columns.
5. The system of claim 3 , wherein each insert table identifies record values of the corresponding inserted record including a primary key value for the corresponding inserted record.
6. The system of claim 3 , wherein each update table identifies the primary key of the updated record and at least one updated value.
7. The system of claim 1 , wherein the delta data structure is a binary tree structure.
8. The system of claim 1 , the memory further comprising instructions that cause the at least one processor to merge information from the differential data structure and the delta data structure into the base data structure to generate an updated base data structure sorted by the primary key.
9. At least one non-transitory machine-readable medium comprising instructions that, when executed by at least one processor; cause the at least one processor to perform operations to:
identify a proposed modification to at least one record of a base data structure including a plurality of records and sorted by primary key of the plurality of records;
identify that a differential data structure corresponds to a type of modification;
add a first record to the differential data structure including a row within the differential data structure and describes the proposed modification;
add a second record to a delta data structure sorted by the primary key that includes a primary key value of the second record, the type of the proposed modification, and a row number of the first record within the differential data structure;
incorporate, upon approval of the proposed modification the proposed modification into a data model using the base data structure, the differential data structure, and the delta data structure; and
delete, upon expiration of a period of time provided for approval of the proposed modification via the data model without approval of the proposed modification, both the first record from the differential data structure and the second record from the delta data structure.
10. The at least one non-transitory machine-readable medium of claim 9 , further comprising instructions that cause the at least one processor to store a copy of the delta data structure and the differential data structure with version data that includes a version of an updated base data structure updated using the delta data structure, wherein the version data is incorporated with the proposed modification into the data model.
11. The at least one non-transitory machine-readable medium of claim 9 , wherein the type of modification is one of a set including insertion of a new record, updating a value of an existing record, and deleting an existing record; and the differential data structure includes at least one delete table, at least one update table, and at least one insert table.
12. The at least one non-transitory machine-readable medium of claim 11 , wherein the base data structure includes a plurality of columns and the at least one update table that comprises a plurality of separate update tables, each update table in the plurality of update tables corresponding to respective updates to a respective one of the plurality of columns.
13. The at least one non-transitory machine-readable medium of claim 11 , wherein each insert table identifies record values of the corresponding inserted record including a primary key value for the corresponding inserted record.
14. The at least one non-transitory machine-readable medium of claim 11 , wherein each update table identifies the primary key of the updated record and at least one updated value.
15. The at least one non-transitory machine-readable medium of claim 9 , wherein the delta data structure is a binary tree structure.
16. The at least one non-transitory machine-readable medium of claim 9 , further comprising instructions that cause the at least one processor to merge information from the differential data structure and the delta data structure into the base data structure to generate an updated base data structure sorted by the primary key.
17. A method comprising:
identifying a proposed modification to at least one record of a base data structure including a plurality of records and sorted by primary key of the plurality of records;
identifying that a differential data structure corresponds to a type of modification;
adding a first record to the differential data structure including a row within the differential data structure and describes the proposed modification;
adding a second record to a delta data structure sorted by the primary key that includes a primary key value of the second record, the type of the proposed modification, and a row number of the first record within the differential data structure;
incorporating, upon approval of the proposed modification, the proposed modification into a data model using the base data structure, the differential data structure, and the delta data structure; and
deleting, upon expiration of a period of time provided for approval of the proposed modification via the data model without approval of the proposed modification, both the first record from the differential data structure and the second record from the delta data structure.
18. The method of claim 17 , further comprising storing a copy of the delta data structure and the differential data structure with version data that includes a version of an updated base data structure updated using the delta data structure, wherein the version data is incorporated with the proposed modification into the data model.
19. The method of claim 17 , wherein the type of modification is one of a set including insertion of a new record, updating a value of an existing record, and deleting an existing record; and
the differential data structure includes at least one delete table, at least one update table, and at least one insert table.
20. The method of claim 19 , wherein the base data structure includes a plurality of columns and the at least one update table that comprises a plurality of separate update tables, each update table in the plurality of update tables corresponding to respective updates to a respective one of the plurality of columns.
21. The method of claim 19 , wherein each insert table identifies record values of the corresponding inserted record including a primary key value for the corresponding inserted record.
22. The method of claim 19 , wherein each update table identifies the primary key of the updated record and at least one updated value.
23. The method of claim 17 , wherein the delta data structure is a binary tree structure.
24. The method of claim 17 , further comprising merging information from the differential data structure and the delta data structure into the base data structure to generate an updated base data structure sorted by the primary key.