[發明專利]基于緩存表構建可達圖的方法

有效

• 申請號: 201910762401.3
• 申請日: 2019-08-19
• 公開（公告）號: CN110543494B
• 公開（公告）日: 2023-03-24
• 發明（設計）人: 陳睿;劉國威;何忠毓;周亞曦;李玲;趙雅利
• 申請（專利權）人: 湖南麟淇網絡科技股份有限公司
• 主分類號: G06F16/2455
• 分類號: G06F16/2455;G06F16/2458;G06F16/28
• 代理公司: 長沙科明知識產權代理事務所(普通合伙) 43203
• 代理人: 吳蘭秀

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

步驟一，構造緩存表：在圖形數據庫或內存中建立一張關系緩存表；所述緩存表由表頭和表體組成，所述表體包括多行條目，所述條目的行數為一個常數C，所述表頭從左至右依次包括：序號、根節點名稱、多個子節點名稱、多個子節點層級、上次訪問時間；

步驟二，使用緩存表構建可達圖；

以根節點構建可達圖時，將首先查詢緩存表中的根節點名稱列，包括以下情況：

情況a：根節點出現在緩存表的所述根節點名稱列，取出緩存表中根節點名稱為該根節點的條目，此行條目包含了以該根節點為根的可達圖的所有信息；

情況b：根節點未出現在緩存表的所述根節點名稱列，按照原有訪問方式逐級遍歷緩存表，并將得到的可達圖返回；

步驟三，更新緩存表。

2.根據權利要求1所述的基于緩存表構建可達圖的方法，其特征在于：

所述序號為在表體的序號列的多行條目內存放條目數；

所述根節點名稱為在表體中的根節點名稱列的多行條目內存放根節點的名稱；

所述多個子節點名稱為在表體中相應子節點名稱列的多行條目內存放子節點的名稱，所述子節點的數目不超過L；

所述多個子節點層級為在表體中相應子節點層級列存放該子節點的層級數，每一所述子節點的層級為該子節點與所述根節點之間的層數；

所述上次訪問時間為在表體中的上次訪問時間列存放上次使用該行條目數據構建可達圖的時間，包括年、月、日、時、分、秒。

3.根據權利要求2所述的基于緩存表構建可達圖的方法，其特征在于：每一所述子節點名稱與子節點層級依次相鄰設置。

4.根據權利要求1所述的基于緩存表構建可達圖的方法，其特征在于：所述步驟三中，以根節點構建可達圖時，將首先查詢緩存表中的根節點名稱列，包括以下情況需要更新緩存表：

情況a：根節點出現在緩存表的所述根節點名稱列，則只需更新緩存表中的所述根節點名稱為該根節點這一行條目的所述上次訪問時間為當前時間；

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

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