[發明專利]一種基于B+樹的ETC收費系統用戶卡狀態名單存取方法

在審

• 申請號: 202211159072.1
• 申請日: 2022-09-22
• 公開（公告）號: CN115510059A
• 公開（公告）日: 2022-12-23
• 發明（設計）人: 鄭文;邱曉東;王玲;王洋洋;史強強;朱國磊
• 申請（專利權）人: 上海電科市政工程有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G07B15/06
• 代理公司: 上海璀匯知識產權代理事務所(普通合伙) 31367
• 代理人: 王文穎

1.一種基于B+樹的ETC收費系統用戶卡狀態名單存取方法，其特征在于，包括以下步驟：

第一步、將用戶卡狀態名單轉化為單鏈數據結構dictionary實例，其中，鏈數據結構dictionary包括用于記錄用戶卡號的key字段、用于記錄用戶卡狀態信息的value字段以及用于存儲指向其它單鏈數據結構dictionary實例的指針的next字段；

第二步、在寫入用戶卡狀態名單時，對于當前單鏈數據結構dictionary實例的處理包括以下步驟：

步驟1、獲得當前單鏈數據結構dictionary實例的key字段的值Key，查找與當前用戶卡槽對應的B+樹實例中各葉子節點的key數組每個key元素值：

若在當前key數組中存在等于值Key的key元素值，則將等于值Key的key元素值定義為當前key元素值，進入步驟6；

若在當前B+樹實例中未查找到等于值Key的key元素值，但在當前key數組中存在小于值Key的key元素值，則將與當前key數組對應的葉子節點作為當前葉子節點，進入步驟3；

若在當前B+樹實例中未查找到小于等于值Key的key元素值，則進入步驟2；

步驟2、新建葉子節點，將新建的葉子節點作為當前葉子節點，進入步驟3；

步驟3、判斷當前葉子節點是否已滿：若當前葉子節點已滿，則分裂當前葉子節點，將分裂得到的葉子節點作為新的當前葉子節點，進入步驟4；若當前葉子節點未滿，則直接進入步驟4；

步驟4、將值Key作為一個key元素值存入當前葉子節點的key數組中，并對key數組中所有key元素值重組排序，獲得重組排序后值Key在當前key數組中的排序序號k，進入步驟5；

步驟5、新建第k個value數組，依據當前單鏈數據結構dictionary實例的next字段，在第k個value數組的對應位置存入當前單鏈數據結構dictionary實例；

步驟6、獲取當前key元素值所對應的value數組及其中存儲的第一個單鏈數據結構dictionary實例，將該單鏈數據結構dictionary實例定義為上一個單鏈數據結構dictionary實例，進入步驟7；

步驟7、若上一個單鏈數據結構dictionary實例的next字段為空，則將上一個單鏈數據結構dictionary實例的next字段指向當前單鏈數據結構dictionary實例，在當前單鏈數據結構dictionary實例存入當前value數組中，且當前單鏈數據結構dictionary實例在當前value數組中的位置位于上一個單鏈數據結構dictionary實例之后；若上一個單鏈數據結構dictionary實例的next字段非空，則進一步獲得單鏈數據結構dictionary實例的next字段指向的下一個單鏈數據結構dictionary實例，將所獲得的下一個單鏈數據結構dictionary實例定義為新的上一個單鏈數據結構dictionary實例后，返回步驟7循環執行；

在查詢查詢用戶卡狀態名單時，在B+樹實例中進行查詢。

2.如權利要求1所述的一種基于B+樹的ETC收費系統用戶卡狀態名單存取方法，其特征在于，第一步中，進行用戶卡狀態名單轉化時，將用戶卡號的前N個字符截取作為用戶卡槽，同一用戶卡槽對應一個B+樹實例，則用戶卡號前四位相同的數據聚合在一個B+樹中；

第二步中，在查詢查詢用戶卡狀態名單時，先將用戶卡號前N個字符截取，命中與其對應的用戶卡槽的B+樹實例，然后在該B+樹實例中進行查詢。

3.如權利要求1所述的一種基于B+樹的ETC收費系統用戶卡狀態名單存取方法，其特征在于，用戶卡號為長度20的數字字符串，則取用戶卡號的前4個字符作為卡槽標記，用戶卡號的后16字符為用戶卡標記，將用戶卡標記轉為long類型，將卡槽標記及轉為long類型的用戶卡標記存儲在所述key字段中。

4.如權利要求1所述的一種基于B+樹的ETC收費系統用戶卡狀態名單存取方法，其特征在于，所述value字段僅用于記錄用戶卡狀態信息中的狀態生效時間、操作類型和操作狀態，且使用計算狀態生效時間+操作狀態*10+操作類型得到長度所得到的15位的long值類型數據存儲在所述value字段中。