Abstract
近年來的資料庫的設計上新發展了一些樹狀的資料結構來解決某些特殊的問題，例如GBD_Tree是為了增進多維的圖形資料之存取效能而設計，而GBD-Tree則是針對便於統計資料而設計的資料結構。由於這些資料結構全是針對單一使用者的環境下所設計，并未解決在多人使用時，所造成的資料不一致(data inconsistency)現象。本篇論文是針對多人使用之環境，提出一個通用的演算法則解決具有下列特性的樹狀結構：(1) 在所有非樹葉節點上，每一個鍵(Key) 皆有一個所關連的加總集合資料，這加總集合資料是由所對應的子樹所加總合成來的。(2) 在每一節點上的鍵皆必須由小到大排列。。目前已找到了BGD-Tree及TBSAM-Tree這兩個樹狀結構可以適用於本篇論文所提出的演算法。本演算法修改了原始的資料結構將每一個節點都加上一個右鍵指標指向右邊的同層節點，配合右移(Moving Right)和鎖耦合(Lock Coupling) 的技巧，來確保資料的一致性及避免死結(Deadlock)的情形發生，并使用四種型態的鎖來達到資料的分享及高度的共時性。GBD-Tree及TBSAM-Tree將用來說明本演算法中的搜尋、插入、刪除、修改及區間處理(range process) 等程序，證明本演算法的正確性及不會發生死結也是本篇的重點。最后，還分析了演算法的執行效能及鎖定結點所須最少的數目。本演算法可以應用大任何具有符合本篇論文所要求特性的樹狀結構上面，只須稍徽修正一下而不必重新改寫。