From d07d6cd3d755ef51c9735bf220c5c32e7326c8fb Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 22 Nov 2019 14:19:14 -0500 Subject: [PATCH] Thoughts: Add retry and rebalance/rebuild nodes. Signed-off-by: Liam R. Howlett --- Thoughts | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) diff --git a/Thoughts b/Thoughts index aa0f534677af..ebba927f3016 100644 --- a/Thoughts +++ b/Thoughts @@ -201,6 +201,23 @@ pointer. Upon allocation failures, the node will continue to contain the XA_DELETED_ENTRY and the parent may require an XA_SKIP_ENTRY if a node is freed. Any gaps that can be combined will be done at the start of a node. +When coalescing, a value may be relocated to a different sub-tree. In this +case, a reader may already be on its way down and 'miss' the move. To avoid +this issue, the special value XA_RETRY_ENTRY is used to indicate a value has +been moved and the walk operation must restart from the root node. + + +Rebalance & Replacing +--------------------- + +Rebalancing occurs if a non-leaf node does not have the minimum number of +occupied slots. Rebalancing occurs by consuming data in the node to the right +into this node. If there is no data left, the right node is freed. If there +is no right node, then rebalancing is done for the left node. If there is a +single node, then the trees height is reduced. When a node is freed, the +parent is also checked for rebalancing. + +Replacing a tree is rarely necessary, however, in the case of a store operation causing an hugely unbalanced tree to be produced, then a rebuild is currently used to restore a compliant B-tree. ***Note that this will be revisited and replaced.*** Worked examples =============== -- 2.50.1