[發(fā)明專利]一種基于內(nèi)存的快速關(guān)系檢索方法

在審

• 申請?zhí)枺?/td>: 202010050321.8
• 申請日: 2020-01-17
• 公開（公告）號: CN111291134A
• 公開（公告）日: 2020-06-16
• 發(fā)明（設(shè)計）人: 李立亞;閭立新;吳麗
• 申請（專利權(quán)）人: 無錫科技職業(yè)學(xué)院
• 主分類號: G06F16/28
• 分類號: G06F16/28;G06F16/2458
• 代理公司: 無錫盛陽專利商標(biāo)事務(wù)所(普通合伙) 32227
• 代理人: 顧吉云;黃瑩

1.一種基于內(nèi)存的快速關(guān)系檢索方法，其包括以下步驟：

S1：確定需要檢索信息的對象作為待檢索實體；

其特征在于，還包括以下步驟：

S2：找到所有的與所述待檢索實體有關(guān)系的抽象實體、實物實體，都將其歸類為關(guān)系實體；

S3：確認(rèn)所有的所述關(guān)系實體之間、所述關(guān)系實體與所述待檢索實體之間的關(guān)系，作為待溯源關(guān)系；

S4:構(gòu)建一維關(guān)系表，所述關(guān)系表的尺寸為TAB_SIZE：

TAB_SIZE＝M*(1+N％)；

式中：M為所述待溯源關(guān)系的數(shù)量，N％為預(yù)留量；

S5：基于TAB_SIZE，在內(nèi)存中為所述一維關(guān)系表分配內(nèi)存，以數(shù)組方式組織內(nèi)存空間；

所述一維關(guān)系表中的每一項為一個二元關(guān)系項，用來存儲兩個實體之間的關(guān)系；

S6：初始化所述二元關(guān)系項的各個字段的值，使其表示未使用：

所述二元關(guān)系項包括字段：

KEY_A、KEY_B、NEXT_A、NEXT_B、P_COM、P_ORD、P_REV的值；

其中：

KEY_A、KEY_B分別是兩個有關(guān)系實體的唯一身份標(biāo)識；

NEXT_A、NEXT_B是兩個指針，分別指向各自實體的下一個二元關(guān)系項，下一個二元關(guān)系項記錄了各自實體與其它實體間的二元關(guān)系，這兩個指針用來構(gòu)造各自實體的二元關(guān)系鏈；

P_COM、P_ORD、P_REV是三個指針，分別指向通用關(guān)系信息塊、從實體A到實體B方向的關(guān)系信息塊、從實體B到實體A方向的關(guān)系信息塊；

S7：取出所述關(guān)系實體中的一個，設(shè)為待追加關(guān)系實體；

S8：取出所述待追加關(guān)系實體與所述待檢索實體之間的所有關(guān)系中的一個，設(shè)為待追加關(guān)系；

S9：獲取所述待追加關(guān)系實體、所述待檢索實體對應(yīng)的唯一身份標(biāo)識；

S10：基于兩個關(guān)系實體的所述唯一身份標(biāo)識，通過哈希算法計算得到位置索引INDEX；

S11：基于所述位置索引INDEX，在所述一維關(guān)系表中存儲所述待追加關(guān)系；

S12：分別構(gòu)建所述待追加關(guān)系實體、所述待檢索實體的二元關(guān)系鏈，將存儲在所述一維關(guān)系表中的所述待追加關(guān)系分別加入到所述待追加關(guān)系實體、所述待檢索實體的二元關(guān)系鏈；

S13：循環(huán)執(zhí)行S8～S12，直至所述待追加關(guān)系實體、所述待檢索實體之間的所有關(guān)系都被追加到所述一維關(guān)系表中；

S14：循環(huán)執(zhí)行S7～S13，直至所有的所述關(guān)系實體與所述待檢索實體之間的所有關(guān)系都被追加到所述一維關(guān)系表中；所述待檢索實體對應(yīng)的所述一維關(guān)系表構(gòu)建完畢；

S15：基于所述一維關(guān)系表進(jìn)行后續(xù)的所述待檢索實體的所有關(guān)系的追溯。

2.根據(jù)權(quán)利要求1所述一種基于內(nèi)存的快速關(guān)系檢索方法，其特征在于：步驟S10中，通過哈希算法計算得到所述位置索引INDEX的方法，包括以下步驟：

a1：比較所述待追加關(guān)系實體、所述待檢索實體對應(yīng)的唯一身份標(biāo)識的大小；

根據(jù)比較結(jié)果，較小的唯一身份標(biāo)識設(shè)置為KEY_A、較大的唯一身份標(biāo)識設(shè)置為KEY_B；

a2：KEY_A在前KEY_B在后，以字符串形式拼接，并去除其中的空格；

a3:使用哈希算法計算KEY_A和KEY_B拼接后的哈希碼；

a4:以該哈希碼模上一維關(guān)系表尺寸TAB_SIZE，得到待確認(rèn)位置索引；

a5:在所述一維關(guān)系表上查看所述待確認(rèn)位置索引對應(yīng)的表項是否已經(jīng)使用：

如果未用，則所述待確認(rèn)位置索引即為所述位置索引INDEX；

否則，如果所述待確認(rèn)位置索引對應(yīng)的表項已經(jīng)被使用，則使用沖突解決算法獲取可用的位置索引，設(shè)置為所述位置索引INDEX。

3.根據(jù)權(quán)利要求2所述一種基于內(nèi)存的快速關(guān)系檢索方法，其特征在于：步驟a5中的所述沖突解決算法使用拉鏈法處理沖突。