[發(fā)明專利]一種樹(shù)結(jié)構(gòu)資源存儲(chǔ)、查詢的方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201410834814.5
• 申請(qǐng)日: 2014-12-26
• 公開(kāi)（公告）號(hào): CN105786931B
• 公開(kāi)（公告）日: 2019-06-04
• 發(fā)明（設(shè)計(jì)）人: 馮孝光;王慶磊;張國(guó)波
• 申請(qǐng)（專利權(quán)）人: 北京神州泰岳軟件股份有限公司
• 主分類號(hào): G06F16/22
• 分類號(hào): G06F16/22
• 代理公司: 北京市隆安律師事務(wù)所 11323
• 代理人: 權(quán)鮮枝;吳昊

1.一種樹(shù)結(jié)構(gòu)資源存儲(chǔ)的方法，其特征在于，包括：

通過(guò)前序遍歷算法遍歷樹(shù)結(jié)構(gòu)資源；

將遍歷出的各個(gè)資源及其各子資源的事件數(shù)據(jù)按照前序遍歷的順序依次存儲(chǔ)在一個(gè)事件列表中；并在一個(gè)位置哈希表中記錄各個(gè)資源在所述事件列表中的起始位置和事件數(shù)量；其中所述事件數(shù)量為各個(gè)資源自身的事件數(shù)量與其各子資源的事件數(shù)量之和；

其中，所述將遍歷出的各個(gè)資源及其各子資源的事件數(shù)據(jù)按照前序遍歷的順序依次存儲(chǔ)在一個(gè)事件列表中；并在一個(gè)位置哈希表中記錄各個(gè)資源在所述事件列表中的起始位置和事件數(shù)量包括：

前序遍歷樹(shù)結(jié)構(gòu)資源時(shí)，將依次遍歷出的當(dāng)前資源的事件數(shù)據(jù)和其各子資源的事件數(shù)據(jù)添加到所述事件列表的尾部；

在所述位置哈希表中記錄該當(dāng)前資源的起始位置和事件數(shù)量；

如果遍歷的當(dāng)前資源存在子資源，則在遍歷完其各子資源時(shí)，使用當(dāng)前資源的事件數(shù)量加上其各子資源的事件數(shù)量來(lái)更新所述位置哈希表中該當(dāng)前資源的事件數(shù)量。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，在通過(guò)前序遍歷算法遍歷樹(shù)結(jié)構(gòu)資源之前，所述方法還包括：

建立一個(gè)空的事件列表，用于按照前序遍歷的順序依次存儲(chǔ)各個(gè)資源及其各子資源的事件數(shù)據(jù)；

建立一個(gè)空的位置哈希表，該位置哈希表的鍵名為各個(gè)資源的ID，鍵值為兩位的整型數(shù)組，用于分別記錄各個(gè)資源在所述事件列表中的起始位置和事件數(shù)量；

將樹(shù)結(jié)構(gòu)資源的事件數(shù)據(jù)加載到緩存中。

3.一種樹(shù)結(jié)構(gòu)資源存儲(chǔ)的裝置，其特征在于，包括：

前序遍歷模塊，用于通過(guò)前序遍歷算法遍歷樹(shù)結(jié)構(gòu)資源；

存儲(chǔ)單元，用于將遍歷出的各個(gè)資源及其各子資源的事件數(shù)據(jù)按照前序遍歷的順序依次存儲(chǔ)在一個(gè)事件列表中，并在一個(gè)位置哈希表中記錄各個(gè)資源在所述事件列表中的起始位置和事件數(shù)量；其中所述事件數(shù)量為各個(gè)資源自身的事件數(shù)量與其各子資源的事件數(shù)量之和；

所述存儲(chǔ)單元包括：

數(shù)據(jù)添加模塊，用于前序遍歷樹(shù)結(jié)構(gòu)資源時(shí)，將依次遍歷出的當(dāng)前資源的事件數(shù)據(jù)和其各子資源的事件數(shù)據(jù)添加到所述事件列表的尾部；

位置記錄模塊，用于在所述位置哈希表中記錄該當(dāng)前資源的起始位置和事件數(shù)量；

數(shù)量更新模塊，用于如果遍歷的當(dāng)前資源存在子資源，則在遍歷完其各子資源時(shí)，使用當(dāng)前資源的事件數(shù)量加上其各子資源的事件數(shù)量來(lái)更新所述位置哈希表中該當(dāng)前資源的事件數(shù)量。

4.根據(jù)權(quán)利要求3 所述的裝置，其特征在于，所述裝置還包括：

建表模塊，用于建立一個(gè)空的事件列表，以按照前序遍歷的順序依次存儲(chǔ)各個(gè)資源及其各子資源的事件數(shù)據(jù)；以及建立一個(gè)空的位置哈希表，該位置哈希表的鍵名為各個(gè)資源的ID，鍵值為兩位的整型數(shù)組，用于分別記錄各個(gè)資源在所述事件列表中的起始位置和事件數(shù)量；

加載模塊，用于在通過(guò)前序遍歷算法遍歷樹(shù)結(jié)構(gòu)資源之前，將樹(shù)結(jié)構(gòu)資源的事件數(shù)據(jù)加載到緩存中。

5.一種樹(shù)結(jié)構(gòu)資源查詢的方法，其特征在于，包括：

獲取預(yù)先存儲(chǔ)的樹(shù)結(jié)構(gòu)資源的事件列表和位置哈希表，其中，所述事件列表中存儲(chǔ)有通過(guò)前序遍歷算法遍歷樹(shù)結(jié)構(gòu)資源時(shí)依次遍歷出的各個(gè)資源及其各子資源的事件數(shù)據(jù)，所述位置哈希表中記錄有各個(gè)資源在所述事件列表中的起始位置和事件數(shù)量；所述事件數(shù)量為各個(gè)資源自身的事件數(shù)量與其各子資源的事件數(shù)量之和；

在所述位置哈希表中查詢待查詢資源在所述事件列表中的起始位置和事件數(shù)量；

根據(jù)查詢出的起始位置和事件數(shù)量，在所述事件列表中截取出該待查詢資源及其各子資源的事件數(shù)據(jù)。