吳鵬洋

摘 要：針對銀行的信用卡BIN數(shù)據(jù)的存儲、增刪和搜索提出一種建立在十叉樹結(jié)構(gòu)的高效處理方法及其相關(guān)算法。該算法具有易用、節(jié)省存儲、快速查詢和可擴(kuò)展的應(yīng)用特征，解決了信用卡BIN數(shù)據(jù)的存儲和搜索效率難題，為信用卡BIN的規(guī)則變化和拓展提供了一種可用的技術(shù)解決方案。

關(guān)鍵詞：信用卡；存儲；十叉樹；卡BIN搜索

1 引言

當(dāng)前中國的信息化發(fā)展很快，信用卡的應(yīng)用范圍和占零售額的比例不斷上升。在信用卡的交易中對信用卡的校驗(yàn)、存儲和快速搜索的要求越來越高，以前交易處理系統(tǒng)簡單地按卡號順序全匹配的方式在大數(shù)據(jù)量的信用卡的系統(tǒng)里越來越不適應(yīng)。快速有效地存儲和搜索方式能有效提升單位時(shí)間交易筆數(shù)，從而提升系統(tǒng)處理性能。

2 信用卡數(shù)據(jù)的算法搜索與增刪

本文在二叉樹的基礎(chǔ)上，針對信用卡行業(yè)的數(shù)據(jù)（通?？ǖ臄?shù)據(jù)主要指卡號或卡BIN，其中卡號長度為13-19位；卡BIN -Bank Identification Number，簡稱 BIN，指信用卡卡號前 6 位、用來區(qū)別發(fā)卡銀行或機(jī)構(gòu)的一套信用卡卡號編碼[3，4]。這些卡數(shù)據(jù)雖然長度不一樣，但數(shù)據(jù)特性，處理方式類似，可互相參考，文后以卡BIN為例展開描述）的存儲、增刪、搜索而提供的一種建立在樹結(jié)構(gòu)基礎(chǔ)上的高效、易用、可擴(kuò)展的算法，并兼顧了空間和時(shí)間的效率。解決了通常情況下大量卡或卡BIN段的存儲空間以及搜索效率難題，也提供了在未來信用卡BIN規(guī)則變化下可靈活拓展的方式，提高了整體的可應(yīng)用性。這些數(shù)據(jù)的特點(diǎn)是都為0-9的數(shù)字組成，數(shù)字重復(fù)性高[5]。本處理方式提供一種高效、易用、靈活的結(jié)構(gòu)來存儲大量的數(shù)據(jù)（如卡BIN），利用樹結(jié)構(gòu)的搜索優(yōu)勢來達(dá)到快速搜索的目的。主要包括十叉樹的創(chuàng)建、十叉樹的搜索以及十叉樹的增刪三個(gè)部分（以下以卡BIN來說明）：

2.1 十叉樹的結(jié)構(gòu)

樹其實(shí)是N（N>=0）個(gè)節(jié)點(diǎn)的有限集合。十叉樹可以看成是二叉樹的應(yīng)用拓展，是滿足有且僅有一個(gè)根節(jié)點(diǎn)，除根節(jié)點(diǎn)之外其余節(jié)點(diǎn)被分成10個(gè)互不相交元素的有限集合，其中每個(gè)集合又是一個(gè)十叉樹。

2.2 十叉樹的創(chuàng)建

置根節(jié)點(diǎn)為（0，0），對于每一個(gè)卡BIN從根節(jié)點(diǎn)出發(fā)，每個(gè)節(jié)點(diǎn)定義為（data，flag），其中data對應(yīng)卡BIN中的一位數(shù)據(jù)。

flag為標(biāo)志位，卡BIN中最后一位數(shù)據(jù)置標(biāo)志位為1，其余為0。創(chuàng)建的流程是讀取每個(gè)卡BIN數(shù)字，然后根據(jù)每一位數(shù)字去判斷節(jié)點(diǎn)是否已存在于樹上，如果已存在標(biāo)記且讀下一個(gè)卡BIN數(shù)字，否則繼續(xù)往下按照樹的結(jié)構(gòu)來創(chuàng)建，由于卡BIN是數(shù)字 集，因此對于每個(gè)父節(jié)點(diǎn)都只存在[0，9]之間最多十棵子樹，則創(chuàng)建完后必然是十叉樹。

2.3 十叉樹的搜索

對于每一個(gè)卡BIN，對十叉樹采用自根向下結(jié)合樹結(jié)構(gòu)的 遍歷算法，根據(jù)卡BIN數(shù)字的位數(shù)來搜索樹的層次，依次匹配樹上每個(gè)節(jié)點(diǎn)（data，flag），如果匹配則以當(dāng)前點(diǎn)為根節(jié)點(diǎn)繼續(xù) 往下搜索下一位卡BIN數(shù)字，直到匹配到卡BIN最后一位數(shù)字 在十叉樹上的標(biāo)志位為1，則搜索成功，否則即為失敗。

2.4 十叉樹的增刪十叉樹的增加

即在搜索的基礎(chǔ)上，針對卡BIN的每一位數(shù)字遍歷十叉樹，匹配每一個(gè)節(jié)點(diǎn)（data，flag），當(dāng)匹配不上時(shí)，按照樹結(jié)構(gòu)建立節(jié)點(diǎn)，直到匹配到最后一位，并置該標(biāo)志位為1；十叉樹的刪除即在搜索的基礎(chǔ)上，針對卡BIN的每一位數(shù)字遍歷十叉樹，匹配每一個(gè)節(jié)點(diǎn)（data，flag），當(dāng)匹配不上時(shí)，退出。直到匹配到最后一位，并置該標(biāo)志位為0。

3 算法比較

當(dāng)前信用卡數(shù)據(jù)的存儲和搜索通常采用數(shù)據(jù)直接原樣存儲，假設(shè)集合內(nèi)有N個(gè)數(shù)據(jù)，則需要N個(gè)空間存儲，由于卡數(shù)量N較大，因此存儲空間的要求較高；其次，從數(shù)組中查找卡數(shù)據(jù)的效率很低，在最壞情況下需要進(jìn)行N次比較。以40萬卡數(shù)據(jù)存儲，如果數(shù)據(jù)原樣存儲需要查找的卡號在第20萬個(gè)數(shù)據(jù)，匹配到數(shù)據(jù)查找次數(shù)為例：數(shù)據(jù)原樣存儲20萬次十叉樹與數(shù)據(jù)的長度有關(guān)，如卡數(shù)據(jù)是234768，查找最多6次；通過此實(shí)例可以看出在這種情況下十叉樹查找次數(shù)遠(yuǎn)遠(yuǎn)少于數(shù)據(jù)原樣存儲次數(shù)。

4 綜合與總結(jié)

本文提出和研究采用十叉樹的結(jié)構(gòu)及其遍歷算法實(shí)現(xiàn)信用卡BIN的存儲和快速匹配在時(shí)空上具有明顯的優(yōu)勢，概述如下：（1）由于金融行業(yè)數(shù)據(jù)膨大且復(fù)雜，傳統(tǒng)的數(shù)字?jǐn)?shù)據(jù)采用容器來存儲，不同的數(shù)據(jù)（如卡BIN）是存放于不同的容器中的，而采用十叉樹來存儲的方式是按BIN的位數(shù)字存儲，這樣不同卡BIN的相同的位數(shù)字有很大一部分是占用相同的空間，因此存儲比傳統(tǒng)方式小很多?？梢源罅抗?jié)省存儲。（2）十叉樹的搜索效率跟基數(shù)N無關(guān)，而是與數(shù)據(jù)（如卡BIN）的長度相關(guān)，不管多大的數(shù)據(jù)最多只會比較（卡BIN）的長度次數(shù)，在大數(shù)據(jù)量的情況下，性能和效果更加突出，更適應(yīng)越來越快的信用卡的發(fā)展。

十叉樹的可拓展性較強(qiáng)。由于是按位數(shù)字存儲，因此修改、增加或刪除數(shù)據(jù)（如卡BIN）時(shí)，只要對位數(shù)字節(jié)點(diǎn)進(jìn)行操作即可，不用修改基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，這樣就節(jié)省了大量的計(jì)算資源。在基于卡BIN是[0，9]的數(shù)字前提下，滿足卡BIN長度及 規(guī)則業(yè)務(wù)的任何變化。

[參考文獻(xiàn)]

[1]郭芳.三種三叉樹存儲結(jié)構(gòu)的比較[J].安康師專學(xué)報(bào)，999（1）.

[2]劉洋.一種統(tǒng)一的二叉樹結(jié)構(gòu)遍歷算法及其實(shí)現(xiàn)[J].贛南師范學(xué)院學(xué)報(bào)，2004（3）.

[3]中國人民銀行.中華人民共和國金融行業(yè)標(biāo)準(zhǔn)《信用卡卡片規(guī)范》（JWT0052-2009）[S].2009-07-01.

[4]中國人民銀行.中華人民共和國金融行業(yè)標(biāo)準(zhǔn)《信用卡發(fā)卡行標(biāo)識代碼及卡號》（JR/T0008-2000）[S].2001-01-01.

[5]全國信用卡辦公室.信用卡磁條信息格式和使用規(guī)范《中國信用卡》[S].2001.