《获取排序的统计数据的方法及排序装置的制作方法》由会员分享，可在线阅读，更多相关《获取排序的统计数据的方法及排序装置的制作方法（8页珍藏版）》请在金锄头文库上搜索。
1、获取排序的统计数据的方法及排序装置的制作方法专利名称：获取排序的统计数据的方法及排序装置的制作方法技术领域：本发明涉及排序技术，尤其涉及一种获取排序的统计数据的方法及排序装置。背景技术：随着计算机和网络通信技术的发展，网络成为人们日常生活、工作中进行交流和沟通的重要工具，使得网络上产生了海量的统计数据，例如，网页的用户浏览量信息数据、网站的用户注册量信息数据、游戏系统中的游戏用户量信息数据以及各游戏用户的积分信息数据、微博账户的访问量信息数据以及粉丝量信息数据等。为了从海量的统计数据中能够快速、有效地获取用户查询所需的数据，更好地为用户提供个性化的服务，需要对网络中产生的海量统计数据进行有效管
2、理。例如，基于一定的排序策略，对海量统计数据进行排序，举例来说，根据存储的游戏系统的各用户的积分信息数据，按照积分从高到低进行排列。这样，在接收到用户的积分排序查询请求时，向用户输出排序前N (统计数据量值)位的积分信息数据，即topN数据。其中，N可以根据实际需要确定，例如，对于游戏系统，可以输出前10000名的游戏用户，即N为10000 ;对于微博，输出粉丝最多的前1000个微博账户，以有效降低用户浏览查询结果所需的时间，便于用户快速定位所需的数据。现有基于存储的统计数据获取排序的统计数据的方法，根据统计数据存储在数据库中还是内存中，对应的技术方案主要包含以下两种。(一 )、对于存储在数据
3、库中的统计数据，将接收的统计数据存储在数据库中，并定期对数据库中存储的统计数据进行排序，以排序结果作为当前排序时间周期至下一排序时间周期内用于查询的近似结果。具体地，该流程包括:步骤001，将实时获取的统计数据存放在第一数据库中，并在第一数据库中维护统计数据；本步骤中，各需要进行排序的网页、网站、游戏系统以及微博等，按照预先设置的策略，将实时发生的相关统计数据发送至排序装置。在排序装置中，采用数据库方式存储接收的统计数据。对统计数据进行维护包括:对统计数据的增加、删除以及修改。其中，以游戏系统中游戏用户的积分为例，统计数据的增加是指新用户获取了新积分，将该游戏用户的新积分存储在数据库中；删除是
4、指游戏用户由于作弊等原因，清空该游戏用户的积分；修改是指现有游戏用户通过游戏获取了新的积分或被罚积分，需要对该游戏用户在数据库中存储的积分进行相应更新。步骤002，按照预先设置的周期，对第一数据库中的统计数据进行排序，获取排序结果，将排序结果存放至第二数据库中；本步骤中，按照预先设置的周期，例如，每天凌晨，对第一数据库中的所有统计数据进行排序，并将排序结果存放在与第一数据库不同的另一个第二数据库中。步骤003，接收排序查询请求，从第二数据库中获取排序查询请求对应的统计数据，输出topN统计数据。本步骤中，在用户需要进行排序查询时，从经过排序的第二数据库中进行查询，即所有获取topN的操作，都从
5、第二数据库中读取。这样，通过设置第一数据库和第二数据库，第一数据库用于存储实时接收的统计数据，第二数据库用于存储对统计数据进行排序的排序结果，从而实现统计数据的排序推荐。由于在计算机中，数据可以存放在内存、硬盘(数据库)、移动设备中，其中，一方面，内存中的数据存储成本最高，移动设备中的数据存储成本最低，即将数据存放在内存中，相对于将数据存放在硬盘中，成本较高。另一方面，内存中的数据访问速度最高，移动设备中的数据访问速度最低。而上述对统计数据进行排序的方法，采用硬盘对统计数据进行存储，虽然存储成本较低，但由于数据访问速度较低，运算性能较低，而统计数据量大，导致排序的时间长，排序效率较低；进一步地
6、，采用定期排序的方法，不能在每次进行topN请求时，对数据库A中的统计数据进行实时排序，使得每次获取的topN统计数据的实时性较差。(二)、为了提高topN统计数据的实时性，采用内存对统计数据进行存储，对于存储在内存中的统计数据，可以使用各种有序数据结构进行维护。例如，可以使用开源键值对(key-value)存储系统软件redis中的设置(zset)维护有序统计数据，其中，统计数据采用键值对方式存储在内存中，zset使用跳表维护有序统计数据。或者，还可以使用二叉树等数据结构对统计数据进行维护。以zset维护有序数据为例，基于存储的统计数据获取排序的统计数据的方法，其流程包括:步骤011，将实时
7、获取的统计数据增加到zset中；步骤012,在zset中维护统计数据；本步骤中，统计数据维护包括:统计数据的增加、删除、修改。内存中统计数据的维护与数据库中统计数据的维护相类似。步骤013,接收排序查询请求,通过排列(range)操作,获取排序查询请求对应的topN统计数据。在该基于存储的统计数据获取排序的统计数据的方法中，采用内存存储统计数据，虽然统计数据访问速度快，但由于所有统计数据都存放在内存中，因而，能够存储的数据量大小受到内存大小的限制，而实际应用中，统计数据量是非常大的，如果数据量达到几十吉(G)、上百G，全部存储在内存，由于内存的价格显著高于硬盘，将造成存储成本显著上升；同时，对
8、存储的全部统计数据进行排序以获取排序的统计数据，排序所需的时间长，排序效率还是较低。发明内容本发明的实施例提供一种获取排序的统计数据的方法，降低排序所需的时间、提高统计数据的排序效率。本发明的实施例还提供一种排序装置，降低排序所需的时间、提高统计数据的排序效率。为达到上述目的，本发明实施例提供的一种获取排序的统计数据的方法，预先在内存中设置用于存储第一阈值统计数据的第一扩展红黑树以及存储第二阈值统计数据的第二扩展红黑树，该方法包括:Al，接收到统计数据后，查询第一扩展红黑树以及第二扩展红黑树，如果未查询到接收的统计数据对应的键，执行步骤BI，如果查询到，执行步骤Cl ；BI，根据接收的统计数据
9、对应的值、第一扩展红黑树存储的各统计数据对应的最小值、第二扩展红黑树存储的各统计数据对应的最小值以及最大值，更新第一扩展红黑树、和/或，第二扩展红黑树中存储的统计数据；Cl，根据接收的统计数据对应的值，更新第一扩展红黑树或第二扩展红黑树中查询到的统计数据；D1，接收到排序查询请求后，在第一扩展红黑树中获取排序查询请求对应的排序的第一阈值的统计数据。其中，所述方法进一步包括:维护第一扩展红黑树以及第二扩展红黑树中存储的统计数据。其中，维护所述统计数据包括:对统计数据执行增加、删除或修改处理。其中，所述对统计数据执行删除处理包括:A31，在第一扩展红黑树中查询待删除统计数据，如果查询到，执行步骤A
10、32，否则，执行步骤A33 ；A32，删除查询得到的统计数据，将第二扩展红黑树中最大值对应的统计数据插入第一扩展红黑树；A33，在第二扩展红黑树中查询待删除统计数据，如果查询到，删除查询得到的统计数据，否则，不作处理。其中，所述步骤BI包括:C11，判断第一扩展红黑树中是否存储满统计数据，如果是，执行步骤C12，如果否，将接收的统计数据存储至第一扩展红黑树；C12，判断接收的统计数据对应的值是否大于第一扩展红黑树存储的各统计数据对应的最小值，如果是，执行步骤C13 ;否则，将接收的统计数据输出至第二扩展红黑树，执行步骤C14 ；C13，将第一扩展红黑树中最小值对应的统计数据输出至第二扩展红黑树
11、，并将接收的统计数据存储至第一扩展红黑树，执行步骤C14 ；C14，判断接收的统计数据对应的值是否大于第二扩展红黑树存储的各统计数据对应的最小值，如果是，执行步骤C15 ;否则，丢弃接收的统计数据；C15，将第二扩展红黑树中最小值对应的统计数据删除，并将接收的统计数据存储至第二扩展红黑树。其中，所述步骤Cl包括:D21，判断是否在第一扩展红黑树中查询到接收的统计数据对应的键，如果是，执行步骤D22，否则，将接收的统计数据输出至第二扩展红黑树，执行步骤D24 ；D22，删除在第一扩展红黑树中查询得到的统计数据，判断接收的统计数据对应的值是否小于第一扩展红黑树中存储的各统计数据对应的最小值、且小于
12、第二扩展红黑树中存储的各统计数据对应的最大值，如果是，执行步骤D23，否则，将接收的统计数据插入第一扩展红黑树；D23，将第二扩展红黑树中最大值对应的统计数据插入第一扩展红黑树，将接收的统计数据插入第二扩展红黑树；D24，删除在第二扩展红黑树中查询得到的统计数据，判断接收的统计数据对应的值是否大于第一扩展红黑树中存储的各统计数据对应的最小值，如果是，执行步骤D25，否贝U，执行步骤D26 ；D25，将第一扩展红黑树中最小值对应的统计数据插入第二扩展红黑树，将接收的统计数据插入第一扩展红黑树；D26，将接收的统计数据插入第二扩展红黑树。其中，所述第一阈值不小于输出的统计数据的数量值，所述第二阈值
13、大于第一阈值。一种排序装置，该排序装置包括:内存模块、统计数据查询模块、新增统计数据处理模块、已有统计数据处理模块以及排序查询模块，其中，内存模块，用于设置存储第一阈值统计数据的第一扩展红黑树以及存储第二阈值统计数据的第二扩展红黑树；统计数据查询模块，用于接收到统计数据后，查询内存模块中的第一扩展红黑树以及第二扩展红黑树，如果未查询到接收的统计数据对应的键，将接收的统计数据输出至新增统计数据处理模块，如果查询到，将接收的统计数据输出至已有统计数据处理模块；新增统计数据处理模块，用于根据接收的统计数据对应的值、第一扩展红黑树存储的各统计数据对应的最小值、第二扩展红黑树存储的各统计数据对应的最小值
14、以及最大值，更新内存模块中第一扩展红黑树、和/或，第二扩展红黑树中存储的统计数据；已有统计数据处理模块，用于根据接收的统计数据对应的值，更新内存模块中第一扩展红黑树或第二扩展红黑树中查询到的统计数据；排序查询模块，用于接收到排序查询请求后，在第一扩展红黑树中获取排序查询请求对应的排序的统计数据。较佳地，所述新增统计数据处理模块包括:第一判断单元、第二判断单元、统计数据第一处理单元、第三判断单元以及统计数据第二处理单元，其中，第一判断单元，用于判断内存模块的第一扩展红黑树中是否存储满统计数据，如果是，将接收的统计数据输出至第二判断单元，如果否，将接收的统计数据存储至第一扩展红黑树；第二判断单元，
15、用于判断接收的统计数据对应的值是否大于第一扩展红黑树存储的各统计数据对应的最小值，如果是，向统计数据第一处理单元输出触发信息；否则，将接收的统计数据分别输出至第二扩展红黑树以及第三判断单元；统计数据第一处理单元，用于接收触发信息，将第一扩展红黑树中最小值对应的统计数据输出至第二扩展红黑树，并将接收的统计数据分别输出至第一扩展红黑树以及第三判断单元；第三判断单元，用于判断接收的统计数据对应的值是否大于第二扩展红黑树存储的各统计数据对应的最小值，如果是，通知统计数据第二处理单元；否则，丢弃接收的统计数据；统计数据第二处理单元，用于接收通知，将第二扩展红黑树中最小值对应的统计数据删除，并将接收的统计
16、数据存储至第二扩展红黑树。较佳地，所述已有统计数据处理模块包括:第四判断单元、第五判断单元、统计数据第三处理单元、第六判断单元、统计数据第四处理单元、统计数据第五处理单元以及统计数据第六处理单元，其中，第四判断单元，用于判断是否在内存模块的第一扩展红黑树中查询到接收的统计数据对应的键，如果是，向统计数据第三处理单元输出触发信息；否则，将接收的统计数据分别输出至第二扩展红黑树以及统计数据第五处理单元，通知统计数据第五处理单元；统计数据第三处理单元，用于接收触发信息，删除在第一扩展红黑树中查询得到的统计数据，将接收的统计数据输出至第五判断单元；第五判断单元，用于判断接收的统计数据对应的值是否小于第一扩展红黑树中存储的各统计数据对应的最小值、且小于第二扩展红黑树中存储的各统计数据对应的最大值，如果是，向统计数据第四处理单元输出触发信息以及接收的统计数据；否则，将接收的统计数据插入第一扩展红黑树；统计数据第四处理单元，用于接收触发信息，将第二扩展红黑树中最大值对应的统计数据插入第一扩展红黑树，将接收的统计数据插入第二扩展红黑树；统计数据第五处理单元，用于
