[發(fā)明專利]基于緩存表構(gòu)建可達(dá)圖的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910762401.3
• 申請(qǐng)日: 2019-08-19
• 公開（公告）號(hào): CN110543494B
• 公開（公告）日: 2023-03-24
• 發(fā)明（設(shè)計(jì)）人: 陳睿;劉國(guó)威;何忠毓;周亞曦;李玲;趙雅利
• 申請(qǐng)（專利權(quán)）人: 湖南麟淇網(wǎng)絡(luò)科技股份有限公司
• 主分類號(hào): G06F16/2455
• 分類號(hào): G06F16/2455;G06F16/2458;G06F16/28
• 代理公司: 長(zhǎng)沙科明知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 43203
• 代理人: 吳蘭秀

1.一種基于緩存表構(gòu)建可達(dá)圖的方法，其特征在于：包括以下步驟：

步驟一，構(gòu)造緩存表：在圖形數(shù)據(jù)庫(kù)或內(nèi)存中建立一張關(guān)系緩存表；所述緩存表由表頭和表體組成，所述表體包括多行條目，所述條目的行數(shù)為一個(gè)常數(shù)C，所述表頭從左至右依次包括：序號(hào)、根節(jié)點(diǎn)名稱、多個(gè)子節(jié)點(diǎn)名稱、多個(gè)子節(jié)點(diǎn)層級(jí)、上次訪問時(shí)間；

步驟二，使用緩存表構(gòu)建可達(dá)圖；

以根節(jié)點(diǎn)構(gòu)建可達(dá)圖時(shí)，將首先查詢緩存表中的根節(jié)點(diǎn)名稱列，包括以下情況：

情況a：根節(jié)點(diǎn)出現(xiàn)在緩存表的所述根節(jié)點(diǎn)名稱列，取出緩存表中根節(jié)點(diǎn)名稱為該根節(jié)點(diǎn)的條目，此行條目包含了以該根節(jié)點(diǎn)為根的可達(dá)圖的所有信息；

情況b：根節(jié)點(diǎn)未出現(xiàn)在緩存表的所述根節(jié)點(diǎn)名稱列，按照原有訪問方式逐級(jí)遍歷緩存表，并將得到的可達(dá)圖返回；

步驟三，更新緩存表。

2.根據(jù)權(quán)利要求1所述的基于緩存表構(gòu)建可達(dá)圖的方法，其特征在于：

所述序號(hào)為在表體的序號(hào)列的多行條目?jī)?nèi)存放條目數(shù)；

所述根節(jié)點(diǎn)名稱為在表體中的根節(jié)點(diǎn)名稱列的多行條目?jī)?nèi)存放根節(jié)點(diǎn)的名稱；

所述多個(gè)子節(jié)點(diǎn)名稱為在表體中相應(yīng)子節(jié)點(diǎn)名稱列的多行條目?jī)?nèi)存放子節(jié)點(diǎn)的名稱，所述子節(jié)點(diǎn)的數(shù)目不超過L；

所述多個(gè)子節(jié)點(diǎn)層級(jí)為在表體中相應(yīng)子節(jié)點(diǎn)層級(jí)列存放該子節(jié)點(diǎn)的層級(jí)數(shù)，每一所述子節(jié)點(diǎn)的層級(jí)為該子節(jié)點(diǎn)與所述根節(jié)點(diǎn)之間的層數(shù)；

所述上次訪問時(shí)間為在表體中的上次訪問時(shí)間列存放上次使用該行條目數(shù)據(jù)構(gòu)建可達(dá)圖的時(shí)間，包括年、月、日、時(shí)、分、秒。

3.根據(jù)權(quán)利要求2所述的基于緩存表構(gòu)建可達(dá)圖的方法，其特征在于：每一所述子節(jié)點(diǎn)名稱與子節(jié)點(diǎn)層級(jí)依次相鄰設(shè)置。

4.根據(jù)權(quán)利要求1所述的基于緩存表構(gòu)建可達(dá)圖的方法，其特征在于：所述步驟三中，以根節(jié)點(diǎn)構(gòu)建可達(dá)圖時(shí)，將首先查詢緩存表中的根節(jié)點(diǎn)名稱列，包括以下情況需要更新緩存表：

情況a：根節(jié)點(diǎn)出現(xiàn)在緩存表的所述根節(jié)點(diǎn)名稱列，則只需更新緩存表中的所述根節(jié)點(diǎn)名稱為該根節(jié)點(diǎn)這一行條目的所述上次訪問時(shí)間為當(dāng)前時(shí)間；

情況b：根節(jié)點(diǎn)未出現(xiàn)在緩存表的所述根節(jié)點(diǎn)名稱列，并且查詢緩存表得到的以該根節(jié)點(diǎn)為根的深度為H的可達(dá)圖的子節(jié)點(diǎn)數(shù)目不超過L，并且緩存表中的條目數(shù)小于C，則將可達(dá)圖的信息填入緩存表中的空行條目；

情況c：根節(jié)點(diǎn)未出現(xiàn)在緩存表的所述根節(jié)點(diǎn)名稱列，并且查詢緩存表得到的以該根節(jié)點(diǎn)為根的深度為H的可達(dá)圖的子節(jié)點(diǎn)數(shù)目不超過L，并且緩存表中的條目數(shù)等于C，則先刪除緩存表中的所述上次訪問時(shí)間最早的條目，再將可達(dá)圖的信息填入緩存表中刪除的條目。