METHOD FOR MANAGING T-TREE INDEX KEY AT DATABASE IN MAIN MEMORY

摘要

PURPOSE: A T-tree index key management method is provided to effectively support a variable length key, a multiple attribute key and an overlapping key in a T-tree widely used in a main memory DBMS as an index structure. CONSTITUTION: The method comprises steps of inserting a newly allocated node in an entry if a root node is a null(101,102), replacing a current node with the root node if the root node is not a null(103), stopping a process if the current node is a null(104), comparing a key value of an entry with a minimum value of the current node if the current node is not a null(105), comparing the key value of the entry with a maximum value of the current node if the key value is larger, replacing the current node with a right side child node of the current node and then returning to the step 104 in the case that the key value is larger and the right side child node exists, inserting the entry in the current node and then stopping the process in the case that the right side child node does not exist and an insertion space exists at the current node, inserting the entry in the current node and then stopping the process in the case that the key value is not larger than the maximum value of the current node and an insertion space exists at the current node, deleting the minimum value at the current node and inserting the entry in the current node in the case that an insertion space does not exist, searching the lowest boundary node from the current node in the case that a left side child node exists at the current node, inserting a minimum of the current node in the case that a space exists at the boundary node, allocating a new node and inserting a minimum value in the space does not exist at the boundary node, checking if a left side child node exists at the current node in the case that the key value of the entry is smaller than a minimum value of the current node(118), replacing the current node with the left side child node in the case that the left side child node exists(119), inserting the entry and stopping the process in the case that the left side child node does not exist and a space exists at the current node(120,121), and allocating a new node, inserting the entry in the new node and stopping the process in the case that a space does not exist(120,122).