[發(fā)明專(zhuān)利]一種基于B+樹(shù)的ETC收費(fèi)系統(tǒng)用戶(hù)卡狀態(tài)名單存取方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202211159072.1
• 申請(qǐng)日: 2022-09-22
• 公開(kāi)（公告）號(hào): CN115510059A
• 公開(kāi)（公告）日: 2022-12-23
• 發(fā)明（設(shè)計(jì)）人: 鄭文;邱曉東;王玲;王洋洋;史強(qiáng)強(qiáng);朱國(guó)磊
• 申請(qǐng)（專(zhuān)利權(quán)）人: 上海電科市政工程有限公司
• 主分類(lèi)號(hào): G06F16/22
• 分類(lèi)號(hào): G06F16/22;G07B15/06
• 代理公司: 上海璀匯知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 31367
• 代理人: 王文穎

相較于內(nèi)存加載結(jié)合hash表的存取方法，本發(fā)明提供的一種基于B+樹(shù)的用戶(hù)卡狀態(tài)名單存取方式取消了hash計(jì)算操作，解決因hash碰撞造成的數(shù)據(jù)沖突。本發(fā)明引入用戶(hù)卡槽的聚合模型，對(duì)相同槽下的b+樹(shù)可以實(shí)現(xiàn)并發(fā)寫(xiě)入，極大地提升數(shù)據(jù)寫(xiě)入性能，加載完成4450萬(wàn)用戶(hù)卡狀態(tài)名單耗時(shí)僅需110秒。結(jié)合b+樹(shù)的存取特性，將用戶(hù)卡狀態(tài)名單單條記錄壓縮到28字節(jié)，全量加載完僅需1.16G內(nèi)存空間，有效的降低了ETC收費(fèi)系統(tǒng)的建設(shè)成本，提升了系統(tǒng)的健壯性和魯棒性。在查詢(xún)效率方面，采用本發(fā)明提供的技術(shù)方案后，單記錄命中耗時(shí)不到1ms，相較于hash查找算法耗時(shí)略有增加，但依然能夠滿(mǎn)足ETC收費(fèi)系統(tǒng)的高效運(yùn)作。

技術(shù)領(lǐng)域

本發(fā)明涉及一種數(shù)據(jù)寫(xiě)入和檢索方法，尤其涉及一種基于B+樹(shù)的高速公路用戶(hù)卡狀態(tài)名單存取方法，屬于智能交通領(lǐng)域。

背景技術(shù)

自2015年9月28日，全國(guó)高速公路電子不停車(chē)收費(fèi)實(shí)現(xiàn)全國(guó)聯(lián)網(wǎng)，用戶(hù)實(shí)現(xiàn)一卡暢行全國(guó)，全國(guó)31個(gè)(省)(直轄市)(自治區(qū))，全部實(shí)現(xiàn)了高速公路ETC聯(lián)網(wǎng)收費(fèi)，實(shí)現(xiàn)全國(guó)高速公路ETC聯(lián)網(wǎng)通行，用戶(hù)在任意省份辦理ETC通行卡，即可通行全國(guó)。

隨著ETC卡發(fā)行量的增加，因用戶(hù)注銷(xiāo)、卡遺失、欠費(fèi)停用等原因被添加用戶(hù)狀態(tài)的用戶(hù)卡信息也隨之增加。截至2022年5月，全國(guó)ETC用戶(hù)卡狀態(tài)名單數(shù)量已達(dá)4450萬(wàn)。

用戶(hù)卡狀態(tài)名單包含以下主要屬性：

1)用戶(hù)卡號(hào)：40字節(jié)長(zhǎng)度的字符串，用于用戶(hù)卡的唯一標(biāo)識(shí)；

2)狀態(tài)名單創(chuàng)建時(shí)間：時(shí)間類(lèi)型，用于標(biāo)識(shí)該狀態(tài)名單的發(fā)布時(shí)間；

3)狀態(tài)名單生效時(shí)間：時(shí)間類(lèi)型，用于標(biāo)識(shí)該狀態(tài)名單的生效時(shí)間；

4)操作類(lèi)型：整數(shù)類(lèi)型，用于標(biāo)識(shí)該狀態(tài)名單的操作類(lèi)型，如卡注銷(xiāo)、余額不足等；

5)操作狀態(tài)：整數(shù)類(lèi)型，用標(biāo)識(shí)該狀態(tài)名單的處理狀態(tài)，如進(jìn)入黑名單、解除黑名單；

6)發(fā)行方：12字節(jié)長(zhǎng)度的字符串，用于標(biāo)識(shí)該用戶(hù)卡所屬發(fā)行單位。

在用戶(hù)卡狀態(tài)名單的設(shè)計(jì)中允許同一張卡存在多個(gè)狀態(tài)，最終的用戶(hù)狀態(tài)由多個(gè)狀態(tài)合并。在ETC收費(fèi)系統(tǒng)中，為了保證車(chē)輛的快速通行，系統(tǒng)處理各環(huán)節(jié)的處理時(shí)效性要求極高。

目前，為了確保ETC收費(fèi)系統(tǒng)的處理效率，用戶(hù)卡狀態(tài)名單采用內(nèi)存加載結(jié)合hash查找的方式實(shí)現(xiàn)。單個(gè)用戶(hù)卡狀態(tài)名單存儲(chǔ)需要使用92字節(jié)——用戶(hù)卡號(hào)40字節(jié)+狀態(tài)名單創(chuàng)建時(shí)間8字節(jié)+狀態(tài)名單生效時(shí)間8字節(jié)+操作類(lèi)型4字節(jié)+操作狀態(tài)4字節(jié)+發(fā)行方12字節(jié)+對(duì)象描述符8字節(jié)+8字節(jié)的hash碼。因此，加載4450萬(wàn)名單共需要3.8G內(nèi)存空間。使用hash表查詢(xún)算法需要計(jì)算用戶(hù)卡號(hào)的hash值，對(duì)于4450萬(wàn)用戶(hù)卡狀態(tài)名單，計(jì)算hash值并加載到內(nèi)存需要耗時(shí)20分鐘左右。

因此，在ETC收費(fèi)系統(tǒng)中使用內(nèi)存加載結(jié)合hash查找實(shí)現(xiàn)用戶(hù)狀態(tài)存取方法存在以下弊端：

1)內(nèi)存占用較大

ETC收費(fèi)系統(tǒng)除用戶(hù)卡狀態(tài)名單外還存在其他需要加載到內(nèi)存的運(yùn)行數(shù)據(jù)，增加內(nèi)存的使用會(huì)提升ETC收費(fèi)系統(tǒng)的建設(shè)成本；同時(shí)較大的內(nèi)存占用不利于軟件常態(tài)化運(yùn)作的管理，在運(yùn)維場(chǎng)景下高內(nèi)存的占用降低了系統(tǒng)的健壯性和魯棒性。

2)hash算法存在hash碰撞，造成不同的用戶(hù)卡號(hào)被計(jì)算為相同的hash值，hash碰撞的存在需要重新設(shè)計(jì)hash跳表來(lái)確保相同hash值下不同用戶(hù)卡號(hào)的映射關(guān)系，提升了軟件代碼的復(fù)雜度，降低了系統(tǒng)的健壯性。

3)加載耗時(shí)需要20分鐘以上的現(xiàn)狀也對(duì)ETC收費(fèi)系統(tǒng)快速運(yùn)作、高效運(yùn)轉(zhuǎn)的要求帶來(lái)較大的挑戰(zhàn)。

綜上所述，在用戶(hù)卡狀態(tài)名單存取場(chǎng)景下，使用內(nèi)存加載結(jié)合hash表的方法很難達(dá)到滿(mǎn)意的效果。

發(fā)明內(nèi)容