Page 217 - 《软件学报》2020年第11期

3532 Journal of Software 软件学报 Vol.31, No.11, November 2020

3. L 0 .delete(y 0 );
4. end if
5. if (VTs(y 0 )≤VTs(Front(y 0 ))∧(VTe(Back(y 0 ))≤VTe(y 0 )) then
6. d 0 =[VTs(Front(y 0 )),VTe(Back(y 0 )));
7. if d 0 ∉L next then
8. L 0 .delete(y 0 );
9. a new PLOB is jointed and formed by the Front(y 0 ) and Back(y 0 );
10. else if d 0 ∈L next then
11. a new PLOB is Linear Order joined and formed by the Front(y 0 ) and Back(y 0 );
12. L next .delete(y 0 );
13. a new L next is Linear Order joined and formed by the Front(d 0 ) and Back(d 0 )
14. end if
15. end if
16. if (VTs(Front(y 0 ))<VTs(y 0 ))∧(VTe(Back(y 0 ))≤VTe(y 0 )) then
17. t 0 =[VTs(Front(y 0 )),VTe(Back(y 0 )));
18. if t 0 ∉L 0 then
19. L next .delete(y 0 );
20. a new PLOB is Linear Order joined and formed by the t 0 joining Front(y 0 ) and Back(y 0 );
21. else if t 0 ∈L 0 then
22. L next .delete(y 0 );
23. a new PLOB is Linear Order joined and formed by the y 0 joining Front(y 0 ) and Back(y 0 );
24. end if
25. end if
例 5:由算法 4 可得,TPindex 在进行删除更新时,同样会引起 3 种不同情况的变化.在第 1 种情况中,在某一线
序分枝汇总删除首元节点或尾元节点而不引起其他分枝的变化.如图 6(a)所示,删除节点[6,10]或删除[7,6],则将
删除节点从原有的线序分枝序列中移除,再由离删除节点最近的其他节点变成新的首元节点或尾元节点;在第 2
种情况中,删除线序分枝内部中的节点,但不引起其他分枝分结构变化.如图 6(b)所示,删除节点[7,9],则在原有的
分枝中,分别断开[7,10]与[7,9]、[7,9]与[7,8]的连接,再将[7,10]与[7,8]进行连接;在第 3 种情况中,删除某一分枝内
部中的节点,会引起其他分枝结构的变化.如图 6(c)所示,删除[3,7]节点,则原有的[2,7]与[3,7]、[3,7]与[3,4]之间的
连接会断开,[2,8]与[2,7]形成新的线序分枝,而在首元节点[3,8]则会断开与[4,8]之间的连接,转向与[3,4]建立连
接,这样[3,8],[3,4]与[4,4]形成新的线序分枝.而断开连接后的[4,8]成为新的首元节点,与[4,7],[5,7],[5,5]构成新的
线序分枝.
综上所述,在 PLOB 的结构基础上,对 TPindex 进行时态数据的增加和删除操作时,只需要对相应的 PLOB
进行时态拼接即可得到更新后的索引结构,而不用对全部的时态数据进行更新,极大地提高了索引的更新效率
和利用效率.设时态索引更新共有 k 个线序分枝,每个分枝中共有 m 个元素,则算法 3 的平均时间复杂度均为
kO(logm),最小的时间复杂度为 O(1).算法 4 的最小时间复杂度也同样为 O(1).可见其具有较好的时态数据维护
效率和性能.