基于信用卡的BIN的算法优化

吴鹏洋

摘 要：针对银行的信用卡BIN数据的存储、增删和搜索提出一种建立在十叉树结构的高效处理方法及其相关算法。该算法具有易用、节省存储、快速查询和可扩展的应用特征，解决了信用卡BIN数据的存储和搜索效率难题，为信用卡BIN的规则变化和拓展提供了一种可用的技术解决方案。

关键词：信用卡；存储；十叉树；卡BIN搜索

1 引言

当前中国的信息化发展很快，信用卡的应用范围和占零售额的比例不断上升。在信用卡的交易中对信用卡的校验、存储和快速搜索的要求越来越高，以前交易处理系统简单地按卡号顺序全匹配的方式在大数据量的信用卡的系统里越来越不适应。快速有效地存储和搜索方式能有效提升单位时间交易笔数，从而提升系统处理性能。

2 信用卡数据的算法搜索与增删

本文在二叉树的基础上，针对信用卡行业的数据（通常卡的数据主要指卡号或卡BIN，其中卡号长度为13-19位；卡BIN -Bank Identification Number，简称 BIN，指信用卡卡号前 6 位、用来区别发卡银行或机构的一套信用卡卡号编码[3，4]。这些卡数据虽然长度不一样，但数据特性，处理方式类似，可互相参考，文后以卡BIN为例展开描述）的存储、增删、搜索而提供的一种建立在树结构基础上的高效、易用、可扩展的算法，并兼顾了空间和时间的效率。解决了通常情况下大量卡或卡BIN段的存储空间以及搜索效率难题，也提供了在未来信用卡BIN规则变化下可灵活拓展的方式，提高了整体的可应用性。这些数据的特点是都为0-9的数字组成，数字重复性高[5]。本处理方式提供一种高效、易用、灵活的结构来存储大量的数据（如卡BIN），利用树结构的搜索优势来达到快速搜索的目的。主要包括十叉树的创建、十叉树的搜索以及十叉树的增删三个部分（以下以卡BIN来说明）：

2.1 十叉树的结构

树其实是N（N>=0）个节点的有限集合。十叉树可以看成是二叉树的应用拓展，是满足有且仅有一个根节点，除根节点之外其余节点被分成10个互不相交元素的有限集合，其中每个集合又是一个十叉树。

2.2 十叉树的创建

置根节点为（0，0），对于每一个卡BIN从根节点出发，每个节点定义为（data，flag），其中data对应卡BIN中的一位数据。

flag为标志位，卡BIN中最后一位数据置标志位为1，其余为0。创建的流程是读取每个卡BIN数字，然后根据每一位数字去判断节点是否已存在于树上，如果已存在标记且读下一个卡BIN数字，否则继续往下按照树的结构来创建，由于卡BIN是数字 集，因此对于每个父节点都只存在[0，9]之间最多十棵子树，则创建完后必然是十叉树。

2.3 十叉树的搜索

对于每一个卡BIN，对十叉树采用自根向下结合树结构的 遍历算法，根据卡BIN数字的位数来搜索树的层次，依次匹配树上每个节点（data，flag），如果匹配则以当前点为根节点继续 往下搜索下一位卡BIN数字，直到匹配到卡BIN最后一位数字 在十叉树上的标志位为1，则搜索成功，否则即为失败。

2.4 十叉树的增删十叉树的增加

即在搜索的基础上，针对卡BIN的每一位数字遍历十叉树，匹配每一个节点（data，flag），当匹配不上时，按照树结构建立节点，直到匹配到最后一位，并置该标志位为1；十叉树的删除即在搜索的基础上，针对卡BIN的每一位数字遍历十叉树，匹配每一个节点（data，flag），当匹配不上时，退出。直到匹配到最后一位，并置该标志位为0。

3 算法比较

当前信用卡数据的存储和搜索通常采用数据直接原样存储，假设集合内有N个数据，则需要N个空间存储，由于卡数量N较大，因此存储空间的要求较高；其次，从数组中查找卡数据的效率很低，在最坏情况下需要进行N次比较。以40万卡数据存储，如果数据原样存储需要查找的卡号在第20万个数据，匹配到数据查找次数为例：数据原样存储20万次十叉树与数据的长度有关，如卡数据是234768，查找最多6次；通过此实例可以看出在这种情况下十叉树查找次数远远少于数据原样存储次数。

4 综合与总结

本文提出和研究采用十叉樹的结构及其遍历算法实现信用卡BIN的存储和快速匹配在时空上具有明显的优势，概述如下：（1）由于金融行业数据膨大且复杂，传统的数字数据采用容器来存储，不同的数据（如卡BIN）是存放于不同的容器中的，而采用十叉树来存储的方式是按BIN的位数字存储，这样不同卡BIN的相同的位数字有很大一部分是占用相同的空间，因此存储比传统方式小很多。可以大量节省存储。（2）十叉树的搜索效率跟基数N无关，而是与数据（如卡BIN）的长度相关，不管多大的数据最多只会比较（卡BIN）的长度次数，在大数据量的情况下，性能和效果更加突出，更适应越来越快的信用卡的发展。

十叉树的可拓展性较强。由于是按位数字存储，因此修改、增加或删除数据（如卡BIN）时，只要对位数字节点进行操作即可，不用修改基础数据结构，这样就节省了大量的计算资源。在基于卡BIN是[0，9]的数字前提下，满足卡BIN长度及 规则业务的任何变化。

[参考文献]

[1]郭芳.三种三叉树存储结构的比较[J].安康师专学报，999（1）.

[2]刘洋.一种统一的二叉树结构遍历算法及其实现[J].赣南师范学院学报，2004（3）.

[3]中国人民银行.中华人民共和国金融行业标准《信用卡卡片规范》（JWT0052-2009）[S].2009-07-01.

[4]中国人民银行.中华人民共和国金融行业标准《信用卡发卡行标识代码及卡号》（JR/T0008-2000）[S].2001-01-01.

[5]全国信用卡办公室.信用卡磁条信息格式和使用规范《中国信用卡》[S].2001.