数据存储方法及装置的制造方法
数据存储方法及装置的制造方法
【技术领域】
[0001] 本发明涉及计算机领域，尤其涉及一种数据存储方法及装置。
【背景技术】
[0002] 现有的数据分析中，一般采用Java、C++、Python等高级语言编写程序进行统计， 例如分布式的MapReduce代码等。但是对于独立用户数的统计，目前最简单也是最常用的 方式之一，是利用各类高级语言中的Set对象存储账户号码，最后取得Set的长度得到唯一 值个数。例如Java语言实现的代码如下：
[0004] 上述方法虽然简单、代码量少，但是在数据量大的情况下，Set对象将消耗过多的 内存，甚至导致内存溢出。
【发明内容】
[0005] 本发明实施例的主要目的是提供一种数据存储方法及装置，旨在减小存储空间。
[0006] 为达到以上目的，本发明实施例提供了一种数据存储方法，包括以下步骤：
[0007] 获取待存储的数据；
[0008] 根据所述待存储的数据，获取所述待存储的数据对应的分段位图中的比特位；
[0009] 将所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0010] 将比特位置位后的分段位图进行存储。
[0011] 本发明实施例还提供了一种数据存储装置，包括：
[0012] 数据获取模块，用于获取待存储的数据；
[0013] 位置查找模块，用于根据所述待存储的数据，获取所述待存储的数据对应的分段 位图中的比特位；
[0014] 置位模块，用于将所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0015] 存储模块，用于将比特位置位后的分段位图进行存储。
[0016] 本发明通过将待存储的数据添加到位图的对应分段位图进行存储，相对于现有技 术的HashSet方式，占用更小的内存，且更为高效。而且通过序列化压缩方法，进一步减少 了占用空间。同时，在将待存储的数据添加到位图中时，已经按统一的运算规则分别添加到 有序的段位图中，则整个位图可以很方便地将所有的数据有序导出。因此，本发明采用分段 位图的存储方式，既能高效和方便的存储，又使得数据可以有序的取出。
【附图说明】
[0017] 图1是本发明数据存储方法所应用的的终端硬件架构示例图；
[0018] 图2是本发明数据存储方法一实施例的流程示意图；
[0019] 图3是本发明数据存储方法中分段位图的结构示例图；
[0020] 图4是本发明数据存储方法中另一实施例存储位图的流程示意图；
[0021] 图5是本发明数据存储方法中找出每个段位图中最左边的第1个非空闲位与最右 边的第1个非空闲位的位图示例图；
[0022] 图6a是采用本发明数据存储方法中的分段位图方式存储数据时的时间消耗与采 用HashSet方式、整段位图方式存储数据时的时间消耗比对示例图；
[0023] 图6b是采用本发明数据存储方法中的分段位图方式存储数据时的内存消耗与采 用HashSet方式、整段位图方式存储数据时的内存消耗比对示例图；
[0024] 图7是本发明数据存储方法中位图的表示结构示例图；
[0025] 图8是本发明数据存储方法另一实施例的流程示意图；
[0026] 图9a是采用本发明数据存储方法中压缩序列化方式存储数据时的序列化时间与 采用Java对象序列化、常规序列化方式存储数据的序列化时间比对示例图；
[0027] 图9b是采用本发明数据存储方法中压缩序列化方式存储数据时的反序列化时间 与采用Java对象序列化、常规序列化方式存储数据的反序列化时间比对示例图；
[0028] 图9c是采用本发明数据存储方法中压缩序列化方式存储数据时的占用空间与采 用常规序列化方式存储数据的占用空间比对示例图；
[0029] 图10是本发明数据存储装置一实施例的功能模块示例图；
[0030] 图11是本发明数据存储装置中存储模块的功能模块示例图；
[0031] 图12是本发明数据存储装置另一实施例的功能模块示例图。
[0032] 本发明目的的实现、功能特点及优点将结合实施例，参照附图做进一步说明。
【具体实施方式】
[0033] 以下结合说明书附图及具体实施例进一步说明本发明的技术方案。应当理解，此 处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0034] 本发明提供了一种数据的存储方法。该数据存储方法用于数据分析，即存储某种 值集合的唯一值个数，并对其进行统计。该数据存储方法可以运行于一个单独的终端中，也 可以运行于多个终端组成的系统中。以下将对终端进行相应的描述。
[0035] 参照图1，提出本发明数据存储方法所应用的终端的结构示例图。该终端可以包括 处理器101、存储模块102、输入模块103、通信模块104、显示模块105等部件。本领域技术 人员可以理解，图1中示出的终端结构并不构成对该终端的限定，该终端还可以包括比图 示更多或更少的部件，或者组合某些部件，或者不同的部件布置。
[0036] 具体地，该存储模块102可用于存储软件程序以及数据。该终端中全部信息，包括 输入的原始数据、软件程序、中间运行结果和最终运行结果都将保存在存储模块102中。处 理器101通过运行存储在存储模块102中的软件程序以及数据，从而执行各种功能应用以 及数据处理。上述存储模块102可以包括一个或一个以上计算机可读存储介质，而且其不 但包括内部存储器，还包括外部存储器。所述内部存储器用来存放处理器当前正在执行的 数据和程序，一旦电源关闭，则内部存储器的数据将丢失。外部存储器一般为非易失性存储 器，可以长期保存信息。例如至少一个磁盘存储器件、闪存器件、或其他易失性固态存储器 件。
[0037] 上述输入模块103可用于接收输入的数字或字符信息，以及产生与用户设置以及 功能控制有关的键盘、鼠标、操作杆、光学或者轨迹球信号输入。以目前常用的触摸屏为例， 该触摸屏可包括触摸检测装置和触摸控制器两个部分。其中，触摸检测装置检测用户的触 摸方位，并检测触摸操作带来的信号，将信号传送给触摸控制器；触摸控制器从触摸检测装 置上接收触摸信息，并将它转换成触点坐标，再送给处理器101，并能接收处理器101发来 的命令并加以执行。可以理解的是，该输入模块可以包括但不限于物理键盘、功能键（比如 音量控制按键、开关按键等)、轨迹球、鼠标、操作杆等中的一种或多种。
[0038] 显示模块105可用于显示由用户输入的信息或提供给用户的信息以及终端的各 种图形用户接口，这些图形用户接口可以由图形、文本、图标、视频和其任意组合来构成。 显示模块105可包括显示面板141，例如LCD(LiquidCrystalDisplay,液晶显示器）、 0LED(0rganicLight-EmittingDiode,有机发光二极管）。可以理解的是，该输入模块103 与显示模块105可以作为两个独立的部件来实现，也可以集成在一起实现输入和输出功 能。
[0039] 上述通信装置104可用于终端与外部通信。该通信装置可包括RF电路、WIFI等等。 其中RF电路可用于收发信息或通话过程中，信号的接收和发送，特别地，将基站的下行信 息接收后，交由一个或者一个以上处理器101处理；另外，将涉及上行的数据发送给基站。 通常，RF电路包括但不限于天线、至少一个放大器、调谐器、一个或多个振荡器、用户身份模 块（SM)卡、收发信机、耦合器、LNA(LowNoiseAmplifier，低噪声放大器 )、双工器等。此 外，RF电路还可以通过无线通信与网络和其他设备通信。所述无线通信可以使用任一通信 标准或协议，包括但不限于GSM(GlobalSystemofMobilecommunication，全球移动通讯 系统）、GPRS(GeneralPacketRadioService，通用分组无线服务）、CDMA(CodeDivision MultipleAccess，码分多址）、WCDMA(WidebandCodeDivisionMultipleAccess,宽 带码分多址）、LTE(LongTermEvolution,长期演进）、电子邮件、SMS(ShortMessaging Service，短消息服务）等。WiFi属于短距离无线传输技术，终端通过WiFi可以帮助用户收 发电子邮件、浏览网页和访问流式媒体等，它为用户提供了无线的宽带互联网访问。可以理 解的是，WiFi并不属于终端的必须构成，完全可以根据需要在不改变发明的本质的范围内 而省略。
[0040] 处理器101是终端的控制中心，利用各种接口和线路连接整个终端的各个部分， 通过运行或执行存储在存储模块102内的软件程序，以及调用存储在存储模块102内的数 据，执行终端的各种功能和处理数据，从而对终端进行整体监控。优选地，该处理器101可 包括一个或多个处理核心，例如处理器101可集成应用处理器和调制解调处理器，其中，应 用处理器主要处理操作系统、用户界面和应用程序等，调制解调处理器主要处理无线通信。 可以理解的是，上述调制解调处理器也可以不集成到处理器101中。
[0041] 终端还包括给各个部件供电的电源模块（比如电池)，该电源模块可以通过电源管 理系统与处理器101逻辑相连，从而通过电源管理系统实现管理充电、放电、以及功耗管理 等功能。电源模块还可以包括一个或一个以上的直流或交流电源、再充电系统、电源故障检 测电路、电源转换器或者逆变器、电源状态指示器等任意组件。尽管未示出，终端还可以包 括摄像头、蓝牙模块等，在此不再赘述。
[0042] 基于上述终端的硬件结构，本发明提出的数据存储方法将运行在该终端上，以下 将结合上述终端的硬件结构，对数据存储方法进行详细的描述。
[0043] 实施例一
[0044] 参照图2,该实施例的数据存储方法包括：
[0045] 步骤S110、获取待存储的数据；
[0046] 该待存储的数据为某种值集合的唯一值个数，例如账户号码、邮箱地址、IP地址、 机器物理编号等等。由于是通过位图对数据进行存储，所以这里的数据类型必须是数字型。 因此，为了保证数据类型均符合要求，本实施例中，在获取待存储的数据时，需判断待存储 的数据类型是否为数字型；若待存储的数据类型为数字型，则不做处理，若待存储的数据类 型不是数字型，则通过相应的算法将其转换为数字型，例如HASH(哈希）算法。
[0047] 步骤S120、根据所述待存储的数据值，获取所述待存储的数据对应的分段位图中 的比特位；
[0048] 为了节省空间，将位图顺序切分成若干个段，成为分段位图。每个分段位图由开始 值S、结束值E确定，区间长度L则为E-S+1。根据所述待存储的数据值大小，判断其落在哪 个段的位图中，然后从该分段位图中找到与待存储的数据值对应的位置。若找不到待存储 的数据值大小所属段的位图，则创建该分段位图，然后从该创建的分段位图中找到与待存 储的数据值对应的位置。
[0049] 步骤S130、将所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0050] 该分段位图中默认均为0,当找到与待存储的数据值对应的比特位时，在该比特位 上置位为1。
[0051] 步骤S140、将比特位置位后的分段位图进行存储。
[0052] 最后的位图可以如图3所示，该位图包括多个分段位图，且每个分段位图的长度L 均为E0+1，每个分段位图的对应比特位上为"0"或"1"。由于采用分段位图对待存储的数 据进行存储，由于不存在的段不用存储，从而可以节省存储空间。
[0053] 以下将以账户号码为例，对本发明的数据存储过程进行具体描述。首先，将在该客 户端上设置数据采集装置，用于采集通过该客户端登录服务器的账户号码，例如"10000"。 然后判断该账户号码落在哪个分段位图中。若每个分段位图的长度L为3000，则可以判断 该账户号码" 10000 "落在第4个分段位图中。然后从该第4个分段位图中找到与" 10000 " 对应的位置，即第4个分段位图中的第1000位。因此，在该第4个分段位图中的第1000位 中置1。若第4个分段位图不存在，则先创建该第4个分段位图，然后在在该第4个分段位 图中的第1000位中置1。该账户号码的存储将用于统计该客户端某段时间用户的活跃度或 者登录用户数。以统计客户端某段时间登录的用户数为例，通过遍历该所有的位图，当位图 中的位为1时，则进行计数。在该所有的位图遍历完后，计数值则为登录的用户数。
[0054] 实施例二
[0055] 考虑到大多数情况下，并非所有分段位图中的所有比特位均被占用。因此本发明 还提供了本发明数据存储方法第二实施例。参照图4所示，该实施例的步骤S140包括：
[0056] 步骤S141、当分段位图的首尾存在空闲比特位时，获取该分段位图中最左边的第 1个非空闲比特位，以及该分段位图中最右边的第1个非空闲比特位；
[0057] 首先，判断该分段位图的首是否存在空闲比特位，若分段位图的首存在空闲比特 位时，则获取该分段位图中最左边的第1个非空闲比特位，即最左边的定位针。具体为：从 该分段位图最左边开始向右移动，直到找到为"1"的比特位，即为最左边的第1个非空闲比 特位。若分段位图的首不存在空闲比特位时，则获取该分段位图中最右边的第1个非空闲 比特位，即最右边的定位针。具体为：从该分段位图最右边开始向左移动，直到找到为"1" 的比特位，即为最右边的第1个非空闲比特位。
[0058] 步骤S142、保存分段位图中最左边的第1个非空闲比特位与最右边的第1个非空 闲比特位之间的比特位。
[0059] 如图5所示，找出分段位图中最左边的第1个非空闲比特位与最右边的第1个非 空闲比特位后，再对其进行保存，即保存图5所示的分段位图中的灰色位。
[0060] 本发明实施例在保存位图时，对分段位图中首尾空闲位不存储，从而进一步节省 了存储空间。
[0061] 本发明通过分段位图，对待存储的数据进行位存储，有效减少了哈希值存储的内 存开销，避免了内存溢出的风险，而且内存开销变化很小，程序更加稳定。位操作进行查找、 新增和统计，也更为高效。
[0062] 以下将通过对某客户端操作日志中的10. 5亿流水进行数十次逐步递增测试：原 始记录数从2700万增加到13. 5亿；独立用户数从1300万增加到1. 46亿；每个账户号码为 4字节正整数，最大账户号码一直为4294967196,最小账户号码一直为0。测试语言为Java， JDK1. 6. 0_23, 64-Bit服务器，测试服务器RAM为32G。分别采用HashSet方式、整段位图方 式以及分段位图方式进行测试后。如图6a及图6b所示，其测试结果具体为：
[0063] (1)采用HashSet方式，虚拟机（JVM)的最大可用堆内存（Heap)为8G。内存消耗 从123. 8M快速增长，在独立用户数达到6500万左右时，抛出Heap溢出错误；期间统计时间 从13. 4秒快速增长到80. 1秒。
[0064] (2)采用整段位图方式，位图总长度为最大无符号整形，即4294967296。内存消耗 一直为512M，统计时间从12秒增加到97. 6秒。
[0065] (3)采用分段位图方式：段长设置为1024K时，内存消耗从301M增加到326. 1M，统 计时间从5. 3秒增加到94. 8秒。
[0066] 由上述测试结果可知，采用分段位图的方式，有效的避免了HashSet方式的内存 溢出错误，并且其时间消耗远小于HashSet方式；同时，分段位图方式的内存消耗小于整段 位图的方式，数据越小或者越集中时，差距越明显。
[0067] 实施例三
[0068] 实际应用中，经常需要对待存储的数据进行存储或者多语言之间共享，故需要将 分段位图序列化成通用的数据格式，以便于存储、传输和多语言解析等。序列化的方式有多 种，比如Java语言中实现Serializable接口，或者采用ProtocolBuffer、Thrift、Avro等 序列化工具。而考虑到位图会被频繁修改，以及可移植性等问题，本实施例未采用上述序列 化格式定义，而是直接采用格式化的字节流。
[0069] 本实施例的分段位图由多个唯一整数段编码（ID)标记的段（Segment)组成，而每 个段（Segment)又由一个定位针（Pin)和若干个块（Block)组成，可以采用如下简单协议组 建字节流：
[0071] 通过上述结构序列化的位图所占用的存储空间会小于直接对包含Hash位图的对 象序列化所占用的存储空间。
[0072] 由于ID、Pin和Block个数各占4个字节，总共12个字节。而并非所有的分段位 图都需要12个字节来存储该3个信息，例如当ID、Pin和Block个数没有超过65536时，则 仅需要1或2个字节即可进行存储，从而存储了空间。而为了标识ID、Pin和Block个数分 别采用了几个字节，需要再存储一个信息Tag。考虑到整型最长只有4个字节，即采用2个 比特即可表示其长度。如下所示：
[0074] 也就是说上述3个ID、Pin和Block个数所采用的字节可以通过一个字节来表示。 例如，要存储ID=1，Pin=258, Block个数=108这3个长度信息，用5个字节表示即可，如图7 所示。由于ID为l，Pin=258，Block个数=108,所以ID用1个字节表示即可，为"00000001"； Pin用2个字节表示即可，为"0000000100000010" ;Block个数用1个字节表示即可，为 "01101100"。而表示ID、Pin和Block个数分别采用了几个字节的Tag则为"00010000"。 因此，上例所述3个4字节的整形，实际只需要用5个字节即可存储，节省了 7个字节的空 间。
[0075] 实施例四
[0076] 由于每个分段位图中可能包含有一些连续空块（SequentialBlankBlocks),如 果对其进行合并，则可以大幅减少存储空间。因此，如图8所示，本实施例中步骤S140之前 包括：
[0077] 步骤S150、获取每个分段位图中的连续空块；
[0078] 步骤S160、将所述连续空块压缩成空快包，且空块包的第1个比特位置位为0,第 2到第8个比特位用于表示空块的个数；同时，数据块的第1个比特位置位为1，第2到第8 个比特位用于表示被占用的数据。
[0079] 由于连续空块的合并，则为了区分空块和数据块，可以用每个块的第一个比特位 进行区分。例如，数据块的第一个比特位为1，而空块的第一个比特位为〇。对连续空块，可 以压缩成一个空块包，空块包的第一个比特位为0,第2到第8个比特位则表示空块的个数。 如此，一个空块包可以表示连续127个空块。若连续空块超过127个，则新增一个空块包， 如此递推。可压缩位图的块定义如下所示：
[0082] 由于是否采用压缩方式，会影响每个块的存放形式，且设定后不可更改，故整个位 图还需要一个是否可压缩的标识，一个字节即可。若标识为压缩时，则空块和数据块的第1 个比特位用于标识是空块还是数据块；若标识为不压缩，则数据块的第1个比特位仍然表 示被占用的数据。
[0083] 采用上述方法对分段位图压缩后，整个位图的序列化格式如下：
[0085] 可以理解的是，上述实施例之间可以单独实施，也可以任意两个或多个相互结合 实施，以达到节省存储空间的目的。
[0086] 以下将采用1，000, 000到50, 000, 000的随机整数填充分段位图，分别采用Java 对象序列化、常规序列化和压缩序列化3种方式进行测试，其序列化时间、反序列化时间和 占用的内存对比如图9a、图9b及图9c所示。由图9a、图9b及图9c可以看出，数据量小的 情况下，压缩序列化方式相比常规序列化方式可以大幅度节省空间，但其序列化的时间会 稍长。
[0087] 综上，本发明数据存储方法相对于现有技术的HashSet方式，占用更小的内存，且 更为高效。而且通过序列化压缩方法，进一步减少了占用空间。同时，用于待存储的数据添 加到位图中时，已经按统一的运算规则分别到有序的段位图中，则整个位图可以很方便地 将所有的数据导出，因此分段位图方式是一种非常高效和方便的存储方法。
[0088] 对应地，本发明还提供了一种数据存储装置。如图10所示，该数据存储装置包括：
[0089] 数据获取模块110,用于获取待存储的数据；
[0090] 位置查找模块120,用于根据所述待存储的数据值，获取所述待存储的数据对应的 分段位图中的比特位；
[0091] 置位模块130,用于在所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0092] 存储模块140,用于对比特位置位后的分段位图进行存储。
[0093] 由于是通过位图对数据进行存储，所以这里的数据类型必须是数字型。因此，为了 保证数据类型均符合要求，本实施例中，在数据获取模块110获取待存储的数据时，需判断 待存储的数据类型是否为数字型；若待存储的数据类型为数字型，则不做处理，若待存储的 数据类型不是数字型，则通过相应的算法将其转换为数字型，例如HASH算法。
[0094] 为了节省空间，将位图顺序切分成若干个段，成为分段位图。每个段由开始值S、结 束值E确定，区间长度L则为E-S+1。位置查找模块120根据所述待存储的数据值大小，判 断其落在哪个段的位图中，然后从该分段位图中找到与待存储的数据值对应的比特位。若 找不到待存储的数据值大小所属段的位图，则创建该分段位图，然后从该创建的分段位图 中找到与待存储的数据值对应的比特位。
[0095] 该分段位图中默认均为0,当位置查找模块120获取到与待存储的数据值对应的 比特位时，上述置位模块130将其置1。然后存储模块140将最后的位图进行存储。由于采 用分段位图对待存储的数据进行存储，由于不存在的分段位图不用存储，从而可以节省存 储空间。
[0096] 进一步地，参照图11，上述存储模块140包括：
[0097] 空闲位查找单元141，用于当分段位图的首尾存在空闲比特位，获取该分段位图中 最左边的第1个非空闲比特位，以及该分段位图中最右边的第1个非空闲比特位；
[0098] 存储单元142,用于保存分段位图中最左边的第1个非空闲比特位与最右边的第1 个非空闲比特位之间的比特位。
[0099] 首先，空闲位查找单元141判断该分段位图的首是否存在空闲比特位，若分段位 图的首存在空闲比特位时，则获取该分段位图中最左边的第1个非空闲比特位，即最左边 的定位针。具体为：从该分段位图最左边开始向右移动，直到找到为"1"的比特位，即为最 左边的第1个非空闲比特位。若 分段位图的首不存在空闲比特位时，则获取该分段位图中 最右边的第1个非空闲比特位，即最右边的定位针。具体为：从该分段位图最右边开始向左 移动，直到找到为"1"的比特位，即为最右边的第1个非空闲比特位。然后存储单元142将 分段位图中最左边的第1个非空闲比特位与最右边的第1个非空闲比特位之间的比特位进 行存储。
[0100] 进一步地，本实施例的分段位图由多个唯一整数段编码（ID)标记的段（Segment) 组成，而每个段（Segment)又由一个定位针（Pin)和若干个块（Block)组成。由于ID、Pin 和Block个数各占4个字节，总共12个字节。而并非所有的段位图都需要12个字节来存 储该3个信息，例如当ID、Pin和Block个数没有超过65536时，则仅需要1或2个字节即 可进行存储，从而存储了空间。而为了标识ID、Pin和Block个数分别采用了几个字节，需 要再存储一个信息Tag。考虑到整型最长只有4个字节，即采用2个比特即可表示其长度。 也就是说上述3个ID、Pin和Block个数所采用的字节可以通过一个字节来表示。
[0101] 进一步地，参照图11，上述数据存储装置还包括：
[0102] 连续空块获取模块150,用于获取分段位图中的连续空块；
[0103] 空块压缩模块160，用于将所述连续空块压缩成空快包，且空块包的第一个比特位 置位为〇,第2到第8个比特位则用于表示空块的个数；
[0104] 为了区分空块和数据块，可以用每个块的第一个比特位进行区分。例如，数据块的 第一个比特位为1，而空块的第一个比特位为0。对连续空块，可以压缩成一个空块包，空块 包的第一个比特位仍为0,第2到第8个比特位则表示空块的个数。如此，一个空块包可以 表示连续127个空块。若连续空块超过127个，则新增一个空块包，如此递推。可压缩位图 的块定义如下所示：
[0106] 由于是否采用压缩方式，会影响每个块的存放形式，且设定后不可更改，故整个位 图还需要一个是否采用压缩的标识，一个字节即可。
[0107] 采用上述方法对分段位图压缩后，整个位图的序列化格式如下：
[0109] 本发明通过将待存储的数据添加到位图的对应分段位图中，从而相对于现有技术 的HashSet方式，占用更小的内存，且更为高效。而且通过序列化压缩方法，进一步减少了 占用空间。同时，在将待存储的数据添加到位图中时，已经按统一的运算规则分别添加到有 序的段位图中，则整个位图可以很方便地将所有的数据有序导出。因此，本发明采用分段位 图的存储方式，既能高效和方便的存储，又使得数据可以有序的取出。
[0110] 需要说明的是，在本文中，术语"包括"、"包含"或者其任何其他变体意在涵盖非排 他性的包含，从而使得包括一系列要素的过程、方法、物品或者装置不仅包括那些要素，而 且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者装置所固有 的要素。在没有更多限制的情况下，由语句"包括一个……"限定的要素，并不排除在包括 该要素的过程、方法、物品或者装置中还存在另外的相同要素。
[0111] 上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。通过以上的实施方 式的描述，本领域的技术人员可以清楚地了解到上述实施例方法可借助软件加必需的通用 硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于 这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品 的形式体现出来，该数据存储装置将包括若干指令，并存储在上述终端的存储模块102中。 该若干指令供上述终端(可以是手机，计算机，服务器，或者网络设备等)的处理器101调用， 以执行本发明各个实施例所述的方法。
[0112] 以上所述仅为本发明的优选实施例，并非因此限制其专利范围，凡是利用本发明 说明书及附图内容所作的等效结构或等效流程变换，直接或间接运用在其他相关的技术领 域，均同理包括在本发明的专利保护范围内。
【主权项】
1. 一种数据存储方法，其特征在于，包括以下步骤： 获取待存储的数据； 根据所述待存储的数据，获取所述待存储的数据对应的分段位图中的比特位； 将所述待存储的数据对应的分段位图中的比特位置位为1; 将比特位置位后的分段位图进行存储。2. 如权利要求1所述的数据存储方法，其特征在于，所述将比特位置位后的分段位图 进行存储包括： 当所述分段位图的首尾存在空闲位，获取该分段位图中最左边的第1个非空闲位，以 及该分段位图中最右边的第1个非空闲位； 保存所述分段位图中最左边的第1个非空闲位与最右边的第1个非空闲位之间的比特 位。3. 如权利要求1所述的数据存储方法，其特征在于，所述分段位图包括多个段，且每个 段包括段编码、定位针、多个块以及表示所述段编码、定位针、块中的字节数的字段标识。4. 如权利要求1-3任一项所述的数据存储方法，其特征在于，所述将比特位置位后的 分段位图进行存储之前包括： 获取每个段位图中的连续空块； 将所述连续空块压缩成空快包，且空块包的第一个比特位置位为〇,第2到第8个比特 位则表示空块的个数；同时，将数据块的第一个比特位置位为1，第2到第8个比特位则表 示被占用的数据。5. 如权利要求1所述的数据存储方法，其特征在于，所述获取待存储的数据之后还包 括： 判断待存储的数据类型是否为数字型； 当待存储的数据类型不是数字型时，则将其转换为数字型的数据。6. -种数据存储装置，其特征在于，包括： 数据获取模块，用于获取待存储的数据； 位置查找模块，用于根据所述待存储的数据，获取所述待存储的数据对应的分段位图 中的比特位； 置位模块，用于将所述待存储的数据对应的分段位图中的比特位置位为1 ; 存储模块，用于将比特位置位后的分段位图进行存储。7. 如权利要求6所述的数据存储装置，其特征在于，所述存储模块包括： 空闲位查找单元，用于当所述分段位图的首尾存在空闲位，获取该分段位图中最左边 的第1个非空闲位，以及该分段位图中最右边的第1个非空闲位； 存储单元，用于保存所述分段位图中最左边的第1个非空闲位与最右边的第1个非空 闲位之间的比特位。8. 如权利要求6所述的数据存储装置，其特征在于，所述分段位图包括多个段，且每个 段包括段编码、定位针、多个块以及表示所述段编码、定位针、块中的字节数的字段标识。9. 如权利要求6-8任一项所述的数据存储装置，其特征在于，还包括： 连续空块获取模块，用于获取每个段位图中的连续空块； 空块压缩模块，用于将所述连续空块压缩成空快包，且空块包的第一个比特位置位为 0,第2到第8个比特位用于表示空块的个数；同时，将数据块的第一个比特位置位为1，第2 到第8个比特位用于表示被占用的数据。10.如权利要求6所述的数据存储装置，其特征在于，还包括数据转换模块：判断所获 取的待存储的数据类型是否为数字型；当待存储的数据类型不是数字型时，则将其转换为 数字型的数据。
【专利摘要】本发明公开一种数据存储方法，包括：获取待存储的数据；根据所述待存储的数据，获取所述待存储的数据对应的分段位图中的比特位；将所述待存储的数据对应的分段位图中的比特位置位为1；将比特位置位后的分段位图进行存储。本发明还公开一种数据存储装置。本发明相对于现有技术的数据存储方式进一步减少了存储空间。
【IPC分类】G06F17/30
【公开号】CN104899204
【申请号】CN201410077706
【发明人】王才平
【申请人】腾讯科技（深圳）有限公司
【公开日】2015年9月9日
【申请日】2014年3月5日
【技术领域】
[0001] 本发明涉及计算机领域，尤其涉及一种数据存储方法及装置。
【背景技术】
[0002] 现有的数据分析中，一般采用Java、C++、Python等高级语言编写程序进行统计， 例如分布式的MapReduce代码等。但是对于独立用户数的统计，目前最简单也是最常用的 方式之一，是利用各类高级语言中的Set对象存储账户号码，最后取得Set的长度得到唯一 值个数。例如Java语言实现的代码如下：
[0004] 上述方法虽然简单、代码量少，但是在数据量大的情况下，Set对象将消耗过多的 内存，甚至导致内存溢出。
【发明内容】
[0005] 本发明实施例的主要目的是提供一种数据存储方法及装置，旨在减小存储空间。
[0006] 为达到以上目的，本发明实施例提供了一种数据存储方法，包括以下步骤：
[0007] 获取待存储的数据；
[0008] 根据所述待存储的数据，获取所述待存储的数据对应的分段位图中的比特位；
[0009] 将所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0010] 将比特位置位后的分段位图进行存储。
[0011] 本发明实施例还提供了一种数据存储装置，包括：
[0012] 数据获取模块，用于获取待存储的数据；
[0013] 位置查找模块，用于根据所述待存储的数据，获取所述待存储的数据对应的分段 位图中的比特位；
[0014] 置位模块，用于将所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0015] 存储模块，用于将比特位置位后的分段位图进行存储。
[0016] 本发明通过将待存储的数据添加到位图的对应分段位图进行存储，相对于现有技 术的HashSet方式，占用更小的内存，且更为高效。而且通过序列化压缩方法，进一步减少 了占用空间。同时，在将待存储的数据添加到位图中时，已经按统一的运算规则分别添加到 有序的段位图中，则整个位图可以很方便地将所有的数据有序导出。因此，本发明采用分段 位图的存储方式，既能高效和方便的存储，又使得数据可以有序的取出。
【附图说明】
[0017] 图1是本发明数据存储方法所应用的的终端硬件架构示例图；
[0018] 图2是本发明数据存储方法一实施例的流程示意图；
[0019] 图3是本发明数据存储方法中分段位图的结构示例图；
[0020] 图4是本发明数据存储方法中另一实施例存储位图的流程示意图；
[0021] 图5是本发明数据存储方法中找出每个段位图中最左边的第1个非空闲位与最右 边的第1个非空闲位的位图示例图；
[0022] 图6a是采用本发明数据存储方法中的分段位图方式存储数据时的时间消耗与采 用HashSet方式、整段位图方式存储数据时的时间消耗比对示例图；
[0023] 图6b是采用本发明数据存储方法中的分段位图方式存储数据时的内存消耗与采 用HashSet方式、整段位图方式存储数据时的内存消耗比对示例图；
[0024] 图7是本发明数据存储方法中位图的表示结构示例图；
[0025] 图8是本发明数据存储方法另一实施例的流程示意图；
[0026] 图9a是采用本发明数据存储方法中压缩序列化方式存储数据时的序列化时间与 采用Java对象序列化、常规序列化方式存储数据的序列化时间比对示例图；
[0027] 图9b是采用本发明数据存储方法中压缩序列化方式存储数据时的反序列化时间 与采用Java对象序列化、常规序列化方式存储数据的反序列化时间比对示例图；
[0028] 图9c是采用本发明数据存储方法中压缩序列化方式存储数据时的占用空间与采 用常规序列化方式存储数据的占用空间比对示例图；
[0029] 图10是本发明数据存储装置一实施例的功能模块示例图；
[0030] 图11是本发明数据存储装置中存储模块的功能模块示例图；
[0031] 图12是本发明数据存储装置另一实施例的功能模块示例图。
[0032] 本发明目的的实现、功能特点及优点将结合实施例，参照附图做进一步说明。
【具体实施方式】
[0033] 以下结合说明书附图及具体实施例进一步说明本发明的技术方案。应当理解，此 处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
[0034] 本发明提供了一种数据的存储方法。该数据存储方法用于数据分析，即存储某种 值集合的唯一值个数，并对其进行统计。该数据存储方法可以运行于一个单独的终端中，也 可以运行于多个终端组成的系统中。以下将对终端进行相应的描述。
[0035] 参照图1，提出本发明数据存储方法所应用的终端的结构示例图。该终端可以包括 处理器101、存储模块102、输入模块103、通信模块104、显示模块105等部件。本领域技术 人员可以理解，图1中示出的终端结构并不构成对该终端的限定，该终端还可以包括比图 示更多或更少的部件，或者组合某些部件，或者不同的部件布置。
[0036] 具体地，该存储模块102可用于存储软件程序以及数据。该终端中全部信息，包括 输入的原始数据、软件程序、中间运行结果和最终运行结果都将保存在存储模块102中。处 理器101通过运行存储在存储模块102中的软件程序以及数据，从而执行各种功能应用以 及数据处理。上述存储模块102可以包括一个或一个以上计算机可读存储介质，而且其不 但包括内部存储器，还包括外部存储器。所述内部存储器用来存放处理器当前正在执行的 数据和程序，一旦电源关闭，则内部存储器的数据将丢失。外部存储器一般为非易失性存储 器，可以长期保存信息。例如至少一个磁盘存储器件、闪存器件、或其他易失性固态存储器 件。
[0037] 上述输入模块103可用于接收输入的数字或字符信息，以及产生与用户设置以及 功能控制有关的键盘、鼠标、操作杆、光学或者轨迹球信号输入。以目前常用的触摸屏为例， 该触摸屏可包括触摸检测装置和触摸控制器两个部分。其中，触摸检测装置检测用户的触 摸方位，并检测触摸操作带来的信号，将信号传送给触摸控制器；触摸控制器从触摸检测装 置上接收触摸信息，并将它转换成触点坐标，再送给处理器101，并能接收处理器101发来 的命令并加以执行。可以理解的是，该输入模块可以包括但不限于物理键盘、功能键（比如 音量控制按键、开关按键等)、轨迹球、鼠标、操作杆等中的一种或多种。
[0038] 显示模块105可用于显示由用户输入的信息或提供给用户的信息以及终端的各 种图形用户接口，这些图形用户接口可以由图形、文本、图标、视频和其任意组合来构成。 显示模块105可包括显示面板141，例如LCD(LiquidCrystalDisplay,液晶显示器）、 0LED(0rganicLight-EmittingDiode,有机发光二极管）。可以理解的是，该输入模块103 与显示模块105可以作为两个独立的部件来实现，也可以集成在一起实现输入和输出功 能。
[0039] 上述通信装置104可用于终端与外部通信。该通信装置可包括RF电路、WIFI等等。 其中RF电路可用于收发信息或通话过程中，信号的接收和发送，特别地，将基站的下行信 息接收后，交由一个或者一个以上处理器101处理；另外，将涉及上行的数据发送给基站。 通常，RF电路包括但不限于天线、至少一个放大器、调谐器、一个或多个振荡器、用户身份模 块（SM)卡、收发信机、耦合器、LNA(LowNoiseAmplifier，低噪声放大器 )、双工器等。此 外，RF电路还可以通过无线通信与网络和其他设备通信。所述无线通信可以使用任一通信 标准或协议，包括但不限于GSM(GlobalSystemofMobilecommunication，全球移动通讯 系统）、GPRS(GeneralPacketRadioService，通用分组无线服务）、CDMA(CodeDivision MultipleAccess，码分多址）、WCDMA(WidebandCodeDivisionMultipleAccess,宽 带码分多址）、LTE(LongTermEvolution,长期演进）、电子邮件、SMS(ShortMessaging Service，短消息服务）等。WiFi属于短距离无线传输技术，终端通过WiFi可以帮助用户收 发电子邮件、浏览网页和访问流式媒体等，它为用户提供了无线的宽带互联网访问。可以理 解的是，WiFi并不属于终端的必须构成，完全可以根据需要在不改变发明的本质的范围内 而省略。
[0040] 处理器101是终端的控制中心，利用各种接口和线路连接整个终端的各个部分， 通过运行或执行存储在存储模块102内的软件程序，以及调用存储在存储模块102内的数 据，执行终端的各种功能和处理数据，从而对终端进行整体监控。优选地，该处理器101可 包括一个或多个处理核心，例如处理器101可集成应用处理器和调制解调处理器，其中，应 用处理器主要处理操作系统、用户界面和应用程序等，调制解调处理器主要处理无线通信。 可以理解的是，上述调制解调处理器也可以不集成到处理器101中。
[0041] 终端还包括给各个部件供电的电源模块（比如电池)，该电源模块可以通过电源管 理系统与处理器101逻辑相连，从而通过电源管理系统实现管理充电、放电、以及功耗管理 等功能。电源模块还可以包括一个或一个以上的直流或交流电源、再充电系统、电源故障检 测电路、电源转换器或者逆变器、电源状态指示器等任意组件。尽管未示出，终端还可以包 括摄像头、蓝牙模块等，在此不再赘述。
[0042] 基于上述终端的硬件结构，本发明提出的数据存储方法将运行在该终端上，以下 将结合上述终端的硬件结构，对数据存储方法进行详细的描述。
[0043] 实施例一
[0044] 参照图2,该实施例的数据存储方法包括：
[0045] 步骤S110、获取待存储的数据；
[0046] 该待存储的数据为某种值集合的唯一值个数，例如账户号码、邮箱地址、IP地址、 机器物理编号等等。由于是通过位图对数据进行存储，所以这里的数据类型必须是数字型。 因此，为了保证数据类型均符合要求，本实施例中，在获取待存储的数据时，需判断待存储 的数据类型是否为数字型；若待存储的数据类型为数字型，则不做处理，若待存储的数据类 型不是数字型，则通过相应的算法将其转换为数字型，例如HASH(哈希）算法。
[0047] 步骤S120、根据所述待存储的数据值，获取所述待存储的数据对应的分段位图中 的比特位；
[0048] 为了节省空间，将位图顺序切分成若干个段，成为分段位图。每个分段位图由开始 值S、结束值E确定，区间长度L则为E-S+1。根据所述待存储的数据值大小，判断其落在哪 个段的位图中，然后从该分段位图中找到与待存储的数据值对应的位置。若找不到待存储 的数据值大小所属段的位图，则创建该分段位图，然后从该创建的分段位图中找到与待存 储的数据值对应的位置。
[0049] 步骤S130、将所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0050] 该分段位图中默认均为0,当找到与待存储的数据值对应的比特位时，在该比特位 上置位为1。
[0051] 步骤S140、将比特位置位后的分段位图进行存储。
[0052] 最后的位图可以如图3所示，该位图包括多个分段位图，且每个分段位图的长度L 均为E0+1，每个分段位图的对应比特位上为"0"或"1"。由于采用分段位图对待存储的数 据进行存储，由于不存在的段不用存储，从而可以节省存储空间。
[0053] 以下将以账户号码为例，对本发明的数据存储过程进行具体描述。首先，将在该客 户端上设置数据采集装置，用于采集通过该客户端登录服务器的账户号码，例如"10000"。 然后判断该账户号码落在哪个分段位图中。若每个分段位图的长度L为3000，则可以判断 该账户号码" 10000 "落在第4个分段位图中。然后从该第4个分段位图中找到与" 10000 " 对应的位置，即第4个分段位图中的第1000位。因此，在该第4个分段位图中的第1000位 中置1。若第4个分段位图不存在，则先创建该第4个分段位图，然后在在该第4个分段位 图中的第1000位中置1。该账户号码的存储将用于统计该客户端某段时间用户的活跃度或 者登录用户数。以统计客户端某段时间登录的用户数为例，通过遍历该所有的位图，当位图 中的位为1时，则进行计数。在该所有的位图遍历完后，计数值则为登录的用户数。
[0054] 实施例二
[0055] 考虑到大多数情况下，并非所有分段位图中的所有比特位均被占用。因此本发明 还提供了本发明数据存储方法第二实施例。参照图4所示，该实施例的步骤S140包括：
[0056] 步骤S141、当分段位图的首尾存在空闲比特位时，获取该分段位图中最左边的第 1个非空闲比特位，以及该分段位图中最右边的第1个非空闲比特位；
[0057] 首先，判断该分段位图的首是否存在空闲比特位，若分段位图的首存在空闲比特 位时，则获取该分段位图中最左边的第1个非空闲比特位，即最左边的定位针。具体为：从 该分段位图最左边开始向右移动，直到找到为"1"的比特位，即为最左边的第1个非空闲比 特位。若分段位图的首不存在空闲比特位时，则获取该分段位图中最右边的第1个非空闲 比特位，即最右边的定位针。具体为：从该分段位图最右边开始向左移动，直到找到为"1" 的比特位，即为最右边的第1个非空闲比特位。
[0058] 步骤S142、保存分段位图中最左边的第1个非空闲比特位与最右边的第1个非空 闲比特位之间的比特位。
[0059] 如图5所示，找出分段位图中最左边的第1个非空闲比特位与最右边的第1个非 空闲比特位后，再对其进行保存，即保存图5所示的分段位图中的灰色位。
[0060] 本发明实施例在保存位图时，对分段位图中首尾空闲位不存储，从而进一步节省 了存储空间。
[0061] 本发明通过分段位图，对待存储的数据进行位存储，有效减少了哈希值存储的内 存开销，避免了内存溢出的风险，而且内存开销变化很小，程序更加稳定。位操作进行查找、 新增和统计，也更为高效。
[0062] 以下将通过对某客户端操作日志中的10. 5亿流水进行数十次逐步递增测试：原 始记录数从2700万增加到13. 5亿；独立用户数从1300万增加到1. 46亿；每个账户号码为 4字节正整数，最大账户号码一直为4294967196,最小账户号码一直为0。测试语言为Java， JDK1. 6. 0_23, 64-Bit服务器，测试服务器RAM为32G。分别采用HashSet方式、整段位图方 式以及分段位图方式进行测试后。如图6a及图6b所示，其测试结果具体为：
[0063] (1)采用HashSet方式，虚拟机（JVM)的最大可用堆内存（Heap)为8G。内存消耗 从123. 8M快速增长，在独立用户数达到6500万左右时，抛出Heap溢出错误；期间统计时间 从13. 4秒快速增长到80. 1秒。
[0064] (2)采用整段位图方式，位图总长度为最大无符号整形，即4294967296。内存消耗 一直为512M，统计时间从12秒增加到97. 6秒。
[0065] (3)采用分段位图方式：段长设置为1024K时，内存消耗从301M增加到326. 1M，统 计时间从5. 3秒增加到94. 8秒。
[0066] 由上述测试结果可知，采用分段位图的方式，有效的避免了HashSet方式的内存 溢出错误，并且其时间消耗远小于HashSet方式；同时，分段位图方式的内存消耗小于整段 位图的方式，数据越小或者越集中时，差距越明显。
[0067] 实施例三
[0068] 实际应用中，经常需要对待存储的数据进行存储或者多语言之间共享，故需要将 分段位图序列化成通用的数据格式，以便于存储、传输和多语言解析等。序列化的方式有多 种，比如Java语言中实现Serializable接口，或者采用ProtocolBuffer、Thrift、Avro等 序列化工具。而考虑到位图会被频繁修改，以及可移植性等问题，本实施例未采用上述序列 化格式定义，而是直接采用格式化的字节流。
[0069] 本实施例的分段位图由多个唯一整数段编码（ID)标记的段（Segment)组成，而每 个段（Segment)又由一个定位针（Pin)和若干个块（Block)组成，可以采用如下简单协议组 建字节流：
[0071] 通过上述结构序列化的位图所占用的存储空间会小于直接对包含Hash位图的对 象序列化所占用的存储空间。
[0072] 由于ID、Pin和Block个数各占4个字节，总共12个字节。而并非所有的分段位 图都需要12个字节来存储该3个信息，例如当ID、Pin和Block个数没有超过65536时，则 仅需要1或2个字节即可进行存储，从而存储了空间。而为了标识ID、Pin和Block个数分 别采用了几个字节，需要再存储一个信息Tag。考虑到整型最长只有4个字节，即采用2个 比特即可表示其长度。如下所示：
[0074] 也就是说上述3个ID、Pin和Block个数所采用的字节可以通过一个字节来表示。 例如，要存储ID=1，Pin=258, Block个数=108这3个长度信息，用5个字节表示即可，如图7 所示。由于ID为l，Pin=258，Block个数=108,所以ID用1个字节表示即可，为"00000001"； Pin用2个字节表示即可，为"0000000100000010" ;Block个数用1个字节表示即可，为 "01101100"。而表示ID、Pin和Block个数分别采用了几个字节的Tag则为"00010000"。 因此，上例所述3个4字节的整形，实际只需要用5个字节即可存储，节省了 7个字节的空 间。
[0075] 实施例四
[0076] 由于每个分段位图中可能包含有一些连续空块（SequentialBlankBlocks),如 果对其进行合并，则可以大幅减少存储空间。因此，如图8所示，本实施例中步骤S140之前 包括：
[0077] 步骤S150、获取每个分段位图中的连续空块；
[0078] 步骤S160、将所述连续空块压缩成空快包，且空块包的第1个比特位置位为0,第 2到第8个比特位用于表示空块的个数；同时，数据块的第1个比特位置位为1，第2到第8 个比特位用于表示被占用的数据。
[0079] 由于连续空块的合并，则为了区分空块和数据块，可以用每个块的第一个比特位 进行区分。例如，数据块的第一个比特位为1，而空块的第一个比特位为〇。对连续空块，可 以压缩成一个空块包，空块包的第一个比特位为0,第2到第8个比特位则表示空块的个数。 如此，一个空块包可以表示连续127个空块。若连续空块超过127个，则新增一个空块包， 如此递推。可压缩位图的块定义如下所示：
[0082] 由于是否采用压缩方式，会影响每个块的存放形式，且设定后不可更改，故整个位 图还需要一个是否可压缩的标识，一个字节即可。若标识为压缩时，则空块和数据块的第1 个比特位用于标识是空块还是数据块；若标识为不压缩，则数据块的第1个比特位仍然表 示被占用的数据。
[0083] 采用上述方法对分段位图压缩后，整个位图的序列化格式如下：
[0085] 可以理解的是，上述实施例之间可以单独实施，也可以任意两个或多个相互结合 实施，以达到节省存储空间的目的。
[0086] 以下将采用1，000, 000到50, 000, 000的随机整数填充分段位图，分别采用Java 对象序列化、常规序列化和压缩序列化3种方式进行测试，其序列化时间、反序列化时间和 占用的内存对比如图9a、图9b及图9c所示。由图9a、图9b及图9c可以看出，数据量小的 情况下，压缩序列化方式相比常规序列化方式可以大幅度节省空间，但其序列化的时间会 稍长。
[0087] 综上，本发明数据存储方法相对于现有技术的HashSet方式，占用更小的内存，且 更为高效。而且通过序列化压缩方法，进一步减少了占用空间。同时，用于待存储的数据添 加到位图中时，已经按统一的运算规则分别到有序的段位图中，则整个位图可以很方便地 将所有的数据导出，因此分段位图方式是一种非常高效和方便的存储方法。
[0088] 对应地，本发明还提供了一种数据存储装置。如图10所示，该数据存储装置包括：
[0089] 数据获取模块110,用于获取待存储的数据；
[0090] 位置查找模块120,用于根据所述待存储的数据值，获取所述待存储的数据对应的 分段位图中的比特位；
[0091] 置位模块130,用于在所述待存储的数据对应的分段位图中的比特位置位为1 ;
[0092] 存储模块140,用于对比特位置位后的分段位图进行存储。
[0093] 由于是通过位图对数据进行存储，所以这里的数据类型必须是数字型。因此，为了 保证数据类型均符合要求，本实施例中，在数据获取模块110获取待存储的数据时，需判断 待存储的数据类型是否为数字型；若待存储的数据类型为数字型，则不做处理，若待存储的 数据类型不是数字型，则通过相应的算法将其转换为数字型，例如HASH算法。
[0094] 为了节省空间，将位图顺序切分成若干个段，成为分段位图。每个段由开始值S、结 束值E确定，区间长度L则为E-S+1。位置查找模块120根据所述待存储的数据值大小，判 断其落在哪个段的位图中，然后从该分段位图中找到与待存储的数据值对应的比特位。若 找不到待存储的数据值大小所属段的位图，则创建该分段位图，然后从该创建的分段位图 中找到与待存储的数据值对应的比特位。
[0095] 该分段位图中默认均为0,当位置查找模块120获取到与待存储的数据值对应的 比特位时，上述置位模块130将其置1。然后存储模块140将最后的位图进行存储。由于采 用分段位图对待存储的数据进行存储，由于不存在的分段位图不用存储，从而可以节省存 储空间。
[0096] 进一步地，参照图11，上述存储模块140包括：
[0097] 空闲位查找单元141，用于当分段位图的首尾存在空闲比特位，获取该分段位图中 最左边的第1个非空闲比特位，以及该分段位图中最右边的第1个非空闲比特位；
[0098] 存储单元142,用于保存分段位图中最左边的第1个非空闲比特位与最右边的第1 个非空闲比特位之间的比特位。
[0099] 首先，空闲位查找单元141判断该分段位图的首是否存在空闲比特位，若分段位 图的首存在空闲比特位时，则获取该分段位图中最左边的第1个非空闲比特位，即最左边 的定位针。具体为：从该分段位图最左边开始向右移动，直到找到为"1"的比特位，即为最 左边的第1个非空闲比特位。若 分段位图的首不存在空闲比特位时，则获取该分段位图中 最右边的第1个非空闲比特位，即最右边的定位针。具体为：从该分段位图最右边开始向左 移动，直到找到为"1"的比特位，即为最右边的第1个非空闲比特位。然后存储单元142将 分段位图中最左边的第1个非空闲比特位与最右边的第1个非空闲比特位之间的比特位进 行存储。
[0100] 进一步地，本实施例的分段位图由多个唯一整数段编码（ID)标记的段（Segment) 组成，而每个段（Segment)又由一个定位针（Pin)和若干个块（Block)组成。由于ID、Pin 和Block个数各占4个字节，总共12个字节。而并非所有的段位图都需要12个字节来存 储该3个信息，例如当ID、Pin和Block个数没有超过65536时，则仅需要1或2个字节即 可进行存储，从而存储了空间。而为了标识ID、Pin和Block个数分别采用了几个字节，需 要再存储一个信息Tag。考虑到整型最长只有4个字节，即采用2个比特即可表示其长度。 也就是说上述3个ID、Pin和Block个数所采用的字节可以通过一个字节来表示。
[0101] 进一步地，参照图11，上述数据存储装置还包括：
[0102] 连续空块获取模块150,用于获取分段位图中的连续空块；
[0103] 空块压缩模块160，用于将所述连续空块压缩成空快包，且空块包的第一个比特位 置位为〇,第2到第8个比特位则用于表示空块的个数；
[0104] 为了区分空块和数据块，可以用每个块的第一个比特位进行区分。例如，数据块的 第一个比特位为1，而空块的第一个比特位为0。对连续空块，可以压缩成一个空块包，空块 包的第一个比特位仍为0,第2到第8个比特位则表示空块的个数。如此，一个空块包可以 表示连续127个空块。若连续空块超过127个，则新增一个空块包，如此递推。可压缩位图 的块定义如下所示：
[0106] 由于是否采用压缩方式，会影响每个块的存放形式，且设定后不可更改，故整个位 图还需要一个是否采用压缩的标识，一个字节即可。
[0107] 采用上述方法对分段位图压缩后，整个位图的序列化格式如下：
[0109] 本发明通过将待存储的数据添加到位图的对应分段位图中，从而相对于现有技术 的HashSet方式，占用更小的内存，且更为高效。而且通过序列化压缩方法，进一步减少了 占用空间。同时，在将待存储的数据添加到位图中时，已经按统一的运算规则分别添加到有 序的段位图中，则整个位图可以很方便地将所有的数据有序导出。因此，本发明采用分段位 图的存储方式，既能高效和方便的存储，又使得数据可以有序的取出。
[0110] 需要说明的是，在本文中，术语"包括"、"包含"或者其任何其他变体意在涵盖非排 他性的包含，从而使得包括一系列要素的过程、方法、物品或者装置不仅包括那些要素，而 且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者装置所固有 的要素。在没有更多限制的情况下，由语句"包括一个……"限定的要素，并不排除在包括 该要素的过程、方法、物品或者装置中还存在另外的相同要素。
[0111] 上述本发明实施例序号仅仅为了描述，不代表实施例的优劣。通过以上的实施方 式的描述，本领域的技术人员可以清楚地了解到上述实施例方法可借助软件加必需的通用 硬件平台的方式来实现，当然也可以通过硬件，但很多情况下前者是更佳的实施方式。基于 这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品 的形式体现出来，该数据存储装置将包括若干指令，并存储在上述终端的存储模块102中。 该若干指令供上述终端(可以是手机，计算机，服务器，或者网络设备等)的处理器101调用， 以执行本发明各个实施例所述的方法。
[0112] 以上所述仅为本发明的优选实施例，并非因此限制其专利范围，凡是利用本发明 说明书及附图内容所作的等效结构或等效流程变换，直接或间接运用在其他相关的技术领 域，均同理包括在本发明的专利保护范围内。
【主权项】
1. 一种数据存储方法，其特征在于，包括以下步骤： 获取待存储的数据； 根据所述待存储的数据，获取所述待存储的数据对应的分段位图中的比特位； 将所述待存储的数据对应的分段位图中的比特位置位为1; 将比特位置位后的分段位图进行存储。2. 如权利要求1所述的数据存储方法，其特征在于，所述将比特位置位后的分段位图 进行存储包括： 当所述分段位图的首尾存在空闲位，获取该分段位图中最左边的第1个非空闲位，以 及该分段位图中最右边的第1个非空闲位； 保存所述分段位图中最左边的第1个非空闲位与最右边的第1个非空闲位之间的比特 位。3. 如权利要求1所述的数据存储方法，其特征在于，所述分段位图包括多个段，且每个 段包括段编码、定位针、多个块以及表示所述段编码、定位针、块中的字节数的字段标识。4. 如权利要求1-3任一项所述的数据存储方法，其特征在于，所述将比特位置位后的 分段位图进行存储之前包括： 获取每个段位图中的连续空块； 将所述连续空块压缩成空快包，且空块包的第一个比特位置位为〇,第2到第8个比特 位则表示空块的个数；同时，将数据块的第一个比特位置位为1，第2到第8个比特位则表 示被占用的数据。5. 如权利要求1所述的数据存储方法，其特征在于，所述获取待存储的数据之后还包 括： 判断待存储的数据类型是否为数字型； 当待存储的数据类型不是数字型时，则将其转换为数字型的数据。6. -种数据存储装置，其特征在于，包括： 数据获取模块，用于获取待存储的数据； 位置查找模块，用于根据所述待存储的数据，获取所述待存储的数据对应的分段位图 中的比特位； 置位模块，用于将所述待存储的数据对应的分段位图中的比特位置位为1 ; 存储模块，用于将比特位置位后的分段位图进行存储。7. 如权利要求6所述的数据存储装置，其特征在于，所述存储模块包括： 空闲位查找单元，用于当所述分段位图的首尾存在空闲位，获取该分段位图中最左边 的第1个非空闲位，以及该分段位图中最右边的第1个非空闲位； 存储单元，用于保存所述分段位图中最左边的第1个非空闲位与最右边的第1个非空 闲位之间的比特位。8. 如权利要求6所述的数据存储装置，其特征在于，所述分段位图包括多个段，且每个 段包括段编码、定位针、多个块以及表示所述段编码、定位针、块中的字节数的字段标识。9. 如权利要求6-8任一项所述的数据存储装置，其特征在于，还包括： 连续空块获取模块，用于获取每个段位图中的连续空块； 空块压缩模块，用于将所述连续空块压缩成空快包，且空块包的第一个比特位置位为 0,第2到第8个比特位用于表示空块的个数；同时，将数据块的第一个比特位置位为1，第2 到第8个比特位用于表示被占用的数据。10.如权利要求6所述的数据存储装置，其特征在于，还包括数据转换模块：判断所获 取的待存储的数据类型是否为数字型；当待存储的数据类型不是数字型时，则将其转换为 数字型的数据。
【专利摘要】本发明公开一种数据存储方法，包括：获取待存储的数据；根据所述待存储的数据，获取所述待存储的数据对应的分段位图中的比特位；将所述待存储的数据对应的分段位图中的比特位置位为1；将比特位置位后的分段位图进行存储。本发明还公开一种数据存储装置。本发明相对于现有技术的数据存储方式进一步减少了存储空间。
【IPC分类】G06F17/30
【公开号】CN104899204
【申请号】CN201410077706
【发明人】王才平
【申请人】腾讯科技（深圳）有限公司
【公开日】2015年9月9日
【申请日】2014年3月5日
最新回复(0)