An Index Structure for Large Order Database Maintenance Using Variants of B Trees

摘要

This study proposes and evaluates a B{sup}+ tree based indexing scheme with the objective of accelerating some major operations such as insertion and retrieval using both primary memory and secondary storage. It also analyzes the effect on non leaf nodes of a B{sup}+ tree as well as the height of tree. It is shown that the non leaf nodes specially the height of B{sup}+ tree has significant effect for insertion and retrieval of key values. In addition, a new data structure and its operations are explained where the non leaf nodes of B{sup}+ tree is replaced by a single list. Cost models are developed for theoretical analysis. Sufficient experimental results are provided to show the performance improvement and the cost models are validated.