[發明專利]一種基于T-lt樹的主存數據庫的索引方法

有效

• 申請號: 200910033414.3
• 申請日: 2009-06-19
• 公開（公告）號: CN101587484A
• 公開（公告）日: 2009-11-25
• 發明（設計）人: 秦小麟;柏傳杰;戴華
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 南京經緯專利商標代理有限公司
• 代理人: 許 方

1.一種基于T-lt樹的主存數據庫的索引方法，其特征在于：T-lt樹的T-lt結點結構與T樹的T結點結構相比，所述T-lt結點還包括一個尾指針，所述尾指針為一后繼指針，當某T-lt結點存在tail結點時，則該T-lt結點的尾指針指向此tail結點；當該T-lt結點沒有tail結點時，則該T-lt結點的尾指針指向直接后繼結點；所述T-lt結點的tail結點與T結點相比還包括一個指向直接后繼結點的指針；所述索引方法包括數據庫查詢操作、關鍵字插入操作、關鍵字刪除操作三個步驟，其中：

(一)數據庫查詢操作步驟：

A、開始操作，設T-lt樹根結點為當前結點；

B、判斷當前結點是否為空，當結果為是，則結束操作，返回未搜索到；當結果為否，進入下一步驟；

C、判斷搜索值是否小于當前結點的最小值，當結果為是，則設左子結點為當前結點，返回步驟B，繼續進行搜索操作；當結果為否，進入下一步驟；

D、判斷搜索值是否大于當前結點的最大值，當結果為是，則設右子結點為當前結點，返回步驟B，繼續進行搜索操作；當結果為否，則進入下一步驟；

E、在當前結點和其tai?l結點中進行二分查找，結束操作，并返回搜索結果；

(二)關鍵字插入操作步驟：

F、開始操作，設T-lt樹根結點為當前結點；重復上述(一)數據庫查詢操作步驟A～E，在E步驟中將當前結點作為范圍結點，不再進行二分查找；

G、判斷是否找到范圍結點，當沒有找到范圍結點，則將搜索路徑中的最后一個結點作為范圍結點，進入下一步驟；

H、當尋找到范圍結點，繼續判斷該范圍結點是否已滿；

①、當該范圍結點未滿，判斷該范圍結點是否含有tail結點或者原始結點未滿；

a、當結果為是，將待插入元素按一定的順序插入范圍結點，結束操作；

b、當結果為否，則在該范圍結點中添加tail結點，使tail結點的尾指針指向原范圍結點的后繼結點，原范圍結點的尾指針則指向該tail結點，然后將待插入值插入到新的范圍結點中，結束操作；

所述原始結點為不含tail結點的T-lt結點部分；

②、當該范圍結點已滿，進行以下操作：

c、通過該范圍結點的tail結點的后繼指針找到其直接后繼結點，然后將tail結點移出，作為其后繼結點的左子結點，最后將待插入元素插入原范圍結點或者新的子結點；

d、判斷T-lt樹是否失去平衡，當樹失去平衡，則進行旋轉操作使樹平衡，然后結束操作；當T-lt樹未失去平衡，則結束操作；

(三)關鍵字刪除操作步驟：

I、開始操作，設T-lt樹根結點為當前結點；重復上述(一)數據庫查詢操作步驟A～E，在E步驟中將當前結點作為范圍結點；

J、判斷是否找到范圍結點，當沒有找到范圍結點，則操作失敗退出；

K、當尋找到范圍結點，在該范圍結點內刪除待刪元素，判斷刪除元素是否會導致下溢；

(1)、如果在該范圍結點內刪除待刪元素不會導致下溢，判斷刪除后是否會導致tail結點為空；

e、當判斷結果不會導致tail結點為空，則結束操作；

f、當判斷結果導致tail結點為空，則刪除該tail結點，結束操作；

(2)、如果在該范圍結點內刪除待刪元素會導致下溢，則判斷該范圍結點是否為內部結點；

g、如果該范圍結點是一個內部結點，進行以下操作：

i通過該范圍結點的后繼指針找到其直接后繼結點；

ii將后繼結點的最小元素移入該范圍結點中；

iii判斷該后繼結點是否為空，如果后繼結點不為空，則直接進入下述L步驟；如果后繼結點為空，則刪除該后繼結點后進入下述L步驟；

h、如果該范圍結點不是一個內部結點，判斷該范圍結點是否為葉子結點：

iv當該范圍結點不是葉子結點，則直接結束操作；

v當該范圍結點是葉子結點，則判斷進行刪除操作后是否會導致該結點為空，如果該結點不為空，則直接進入下述L步驟；如果該結點為空，則刪除該結點后進入下述L步驟；

L、判斷T-lt樹是否失去平衡，當樹失去平衡，則進行旋轉操作使樹平衡，然后結束操作；當T-lt樹未失去平衡，則結束操作。