[發明專利]基于固態硬盤的高維數據索引結構設計方法

有效

• 申請號: 201110452044.4
• 申請日: 2011-12-29
• 公開（公告）號: CN102542057A
• 公開（公告）日: 2012-07-04
• 發明（設計）人: 崔斌;呂雁飛;李井
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩

1.一種基于固態硬盤的高維數據索引結構設計方法，其特征在于，包括步驟：

將索引結構分為原始R樹區和節點差異日志區兩個部分，分別存儲原始版本數據和原始版本與最近版本的差異日志；

在內存中設計一個哈希表來存儲節點及其更新在所述節點差異日志區存儲位置對應關系的信息；一旦一個新的更新完成，讀出這個節點更早時候的更新日志，然后將其和現在的日志合并并重新存入，作為到目前為止該節點的所有更新日志。

2.如權利要求1所述的方法，其特征在于，所述節點差異日志區分為日志頁來進行使用，一個日志頁能夠存儲多個節點差異的信息。

3.如權利要求1所述的方法，其特征在于，當日志達到一定量時，將所述節點差異日志區與原始R樹區進行合并日志操作。

4.如權利要求1所述的方法，其特征在于，每次更新包括多個更新項，每個更新項記錄了對R樹節點的一個分支的更新操作，包括三種不同的更新操作：插入分支、更新分支和刪除分支。

5.如權利要求4所述的方法，其特征在于，每個更新項的前兩位標識操作類型，接下來的位標識分支號和值。

6.如權利要求5所述的方法，其特征在于，對同一分支的更新會合并成一個更新項記錄，記錄的值為最后更新的值。

7.如權利要求1所述的方法，其特征在于，該索引結構滿足應用程序查詢請求的方法包括步驟：

讀取節點的號；

讀出該節點原始版本信息；

查詢哈希表中該節點對應的日志；

如果有對應的日志項，讀取日志項；

將原始版本與日志合并；

輸出該節點的最新版本。

8.如權利要求1所述的方法，其特征在于，該索引結構滿足應用程序更新請求的方法包括步驟：

輸入待處理的更新請求；

找到更新請求對應的節點；

調用R的更新算法，計算出該節點當前版本；

將當前版本與基準版本比較記錄差異；

查出原有差異日志項；

記錄新的差異日志項，并將原有項作廢；

更新哈希表項；

如果日志區總大小超過限制，執行合并日志操作。

9.如權利要求1所述的方法，其特征在于，用R樹的其他變種，包括R+樹、R*樹來替代R樹。