Browse Prior Art Database

Recoverable Pruning Scheme for Balanced Index Trees

IP.com Disclosure Number: IPCOM000115642D
Original Publication Date: 1995-Jun-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Garg, R: AUTHOR

Abstract

Disclosed is an efficient recoverable Balanced Index Tree pruning scheme. If the pruning of the Index tree is interrupted causing structural errors in the index, then, with the minimal knowledge of what key was being deleted, the operation can be completed and the index structure can be fixed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Recoverable Pruning Scheme for Balanced Index Trees

Disclosed is an efficient recoverable Balanced Index Tree pruning scheme. If the pruning of the Index tree is interrupted causing structural errors in the index, then, with the minimal knowledge of what key was being deleted, the operation can be completed and the index structure can be fixed.

Index trees are widely used in computer science for efficient access to data items associated with keys. It is assumed that the non-leaf nodes in the index tree contain vertical pointers to children nodes, and nodes on each level of the tree point to their right sibling (if any) using horizontal pointers. It is further assumed that the root of each sub-tree in the index contains a key, called the high key, which is greater than or equal to all the keys in the sub-tree.

Key deletions from a balanced index tree may cause a given sub-tree of a balanced index tree to contain no more pointers to data items. In this case the sub-tree needs to be pruned out of the index. To keep the index tree balanced, the key range occupied by the empty tree is split in half and assigned to the neighbor nodes. Pruning is not an atomic operation since it requires more than one node to be updated -- the horizontal pointer of each node to the immediate left of the empty sub tree has to be updated to point beyond the empty sub-tree, the high key in each of these nodes also has to be updated to split the key range of the empty tree, and the vertical pointer in the parent node pointing to the empty tree has to be deleted. In addition, the storage occupied by the empty tree has to be released.

If these updates are interrupted, then the index can have structural errors in it. The recovery scheme described in this disclosure, can recover the index from such structural errors. It relies on the following being done at the time of pruning: 1. the key being deleted is recorded some where, and

2. the first and the last children sub-trees of a parent node are

never deleted, and

3. before the horizontal pointer of any node is changed, a field in

that node called the old-horizontal pointer is set to the old

value of the horizontal pointer, and

4. the nodes are updated bottom-up -- a child node is updated

before its parent.

If pruning follows these conventions, then, when pruning recovery is invoked, the index can be in one of the following four possible stat...