吳鵬洋

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

關鍵詞：信用卡；存儲；十叉樹；卡BIN搜索

1 引言

當前中國的信息化發(fā)展很快，信用卡的應用范圍和占零售額的比例不斷上升。在信用卡的交易中對信用卡的校驗、存儲和快速搜索的要求越來越高，以前交易處理系統(tǒng)簡單地按卡號順序全匹配的方式在大數(shù)據(jù)量的信用卡的系統(tǒng)里越來越不適應?？焖儆行У卮鎯退阉鞣绞侥苡行嵘龁挝粫r間交易筆數(shù)，從而提升系統(tǒng)處理性能。

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

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

2.1 十叉樹的結構

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

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

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

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

2.3 十叉樹的搜索

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

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

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

3 算法比較

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

4 綜合與總結

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

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

[參考文獻]

[1]郭芳.三種三叉樹存儲結構的比較[J].安康師專學報，999（1）.

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

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

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

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