Adding, Deleting, Modifying, and Querying RCR UB-Tree

Insert: The insertion logic of UB-tree is basically not changed, except that you need to directly obtain the transaction information and fill in the xmin column during index insertion.
Delete: The index deletion process is added to the UB-tree. The main procedure of index deletion is similar to that of index insertion. That is, obtain the transaction information, fill in the xmax column, and update active_tuple_count on pages. If the value of active_tuple_count is reduced to 0, the system attempts to recycle the page. (The B-tree index does not maintain the version information and therefore no deletion operation is required.)
Update: For Ustore, data update operations on UB-tree index columns are different from those for Astore. Data updates include index column update and non-index column update. The following figure shows the processing of UB-tree data update.

The preceding figure shows the differences between UB-tree updates on index columns and non-index columns.
- In the case of non-index column updates, the index does not change. The index tuple still points to the data tuple inserted for the first time. No data tuple is inserted to the Uheap. Instead, the Uheap modifies the current data tuple and saves historical data to the undo segment.
- In the case of index column updates, a new index tuple is inserted into UB-tree and points to the same data line pointer and data tuple. To scan the historical data, you need to read it from the undo segment.
Scan: When reading data, you can use index scan to accelerate data read. The UB-tree supports multi-version management and visibility check of index data. The visibility check at the index layer improves the performance of index scan and index-only scan.
For index scanning:
- If the index column contains all columns to be scanned (index-only scanning), binary search is performed on indexes based on the scanning conditions. If a tuple that meets the conditions is found, data is returned.
- If the index column does not contain all columns to be scanned (index scanning), binary search is performed on indexes based on the scanning conditions to find TIDs of the tuples that meet the conditions, and then the corresponding data tuples are found in data tables based on the TIDs. See the following figure.