RCR UB-Tree Space Management

Currently, Astore indexes depend on AutoVacuum and Free Space Map (FSM) for space management, which may not be recycled in a timely manner. Ustore indexes use UB-tree Recycle Queue (URQ), a data structure based on cyclic queues, that is, dual-loop queues, to manage idle index space. The URQ contains two circular queues: potential empty page queue and available empty page queue. Completing space management of indexes in a DML process can effectively alleviate the sharp space expansion caused during the DML process. The index recycling queue is separately stored in the FSM file corresponding to the B-tree index.

As shown in the preceding figure, the index pages flow in the URQ as follows:

1. From an empty page a potential queue

   The index page tail column records the number of active tuples (activeTupleCount) on the page. During the DML process, all tuples on a page are deleted, that is, when activeTupleCount is set to 0, the index page is placed in the potential queue.

2. From the potential queue to an available queue

   The flow from a potential queue to an available queue mainly achieves an income and expense balance for the potential queue and ensure that pages are available for the available queue. That is, after an index empty page is used up in an available queue, at least one index page is transferred from a potential queue to the available queue. Besides, if a new index page is added to a potential queue, at least one index page can be removed from the potential queue and inserted into the available queue.

3. From the available queue to an empty page

   When obtaining an empty index page, the index first searches the available queue for an index page that can be reused. If a page is found, the page is reused. If no page can be reused, physical page extension is performed.