第二届中国软件杯大学生软件设计大赛比赛题目二基于二维数据的快速存贮和查询方法.pdf

《第二届中国软件杯大学生软件设计大赛比赛题目二基于二维数据的快速存贮和查询方法.pdf》由会员分享，可在线阅读，更多相关《第二届中国软件杯大学生软件设计大赛比赛题目二基于二维数据的快速存贮和查询方法.pdf（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、.比赛题目二：基于二维数据的快速存贮和查询方法 2013-01-30 16:10:28来源:浏览:3054次 第二届“中国软件杯大学生软件设计大赛赛题 基于二维数据的快速存贮和查询方法 赛题简介：介绍整个赛题的思路和整体要求 无论是传统的关系数据库、内存数据库，还是实时系统中常用的实时数据库，又或是目前流行的 NoSQL 数据库，索引都是非常重要的数据结构。常见的索引结构 有 HASH 表，AVL 树，红黑树，b 树，b+树，t 树，r 树等,这些树通过对现有的数据结构添加索引信息，以达到快速查询的目的。在数据库中，可以利用索引快速访问数据库表中的特定信息。索引是对数据库表中一个或多个列的值进

2、行排序的结构。比如，想按特定职员的姓来查找他/她，相比于在表中搜索所有的行，对姓建立专门的索引可以极大的提升查询效率。索引提供指针以指向存储在表中指定列的数据值，然后根据指定的排序次序排列这些指针。数据库使用索引的方式与使用书的目录很相似：通过搜索索引找到特定的值，然后跟随指针到达包含该值的行。赛题业务场景：描述赛题相关的真实企业业务背景。从真实场景中，适当简化或者提炼出适合比赛的赛题场景 二 维 数据 主 要来 自 于一 类 按照 时 间周 期 返回 数 据的 传 感器，这类传 感 器会 被 安装 在 需要 实 时监 测 的设备上，比 如 仪表盘、锅炉等，通过 传 感器 传 回监 测 设备

3、的 属性数 据，比如某 一 时time 1 time 2 time 3 time N.刻 的 温度、锅炉的 压 力等，系统可 以 完整 的 记录 下 设备 的 整个 运 行状况，在设 备 出现 问 题时 可 以通 过 历史 记 录进 行 问题 分 析和 问 题定位。当前 的 应用 发展趋 势 表明，被监测 个 体的 数 目正 在 迅速增长，同 时 随着 技 术的 进 步以 与 应用 的 需求，数据回 传 的周 期 也越 来 越短。本 题 对设 备 数据 做 如下定义：struct Data.long long time;float value;其中time代 表 位于 采 集器 数 据采 集

4、时的 绝 对时 间，value表示 在 采集 时 刻采 集 器采 集 到的 属 性数据，因此 同 一采 集 器一 组 按时 序 排列的Data可以 看 做是 一个设 备 在一 段 时间 内 的运 行 状况。这样不 同 设备 的 的time和value的序 列 组合 成 为如 下 所示 的 二.维 表 结构：点名 Point1 value1 value2 value3 valueN Point2 value1 value2 value3 valueN Point3 value1 value2 value3 valueN value1 value2 value3 valueN PointN val

5、ue1 value2 value3 valueN 题目要 XX 现一套针对多个监测设备的采集数据的存储和查询算法，在保证数据能够高速存储到磁盘的同时，对这些磁盘上的数据，能够分别进行按时间维度或者 测点维度的查询，如查询一个 Point一段时间内的所有数据，或者查询某个时刻所有 Point 的数据，不同纬度的查询都有较高的查询速率。功能性需求 假设存在10000个监测设备，对每个设备使用随机数方式生产10000 个属性数据,每个设备时间间隔固定,不同设备时间间隔不一样，针对这些数据实现二维数据的存储和查询设计。随机生成属性数据时同步记录原始数据,数据存储完成后采用单设备一段时间内数据查询与批量

6、设备某一时刻数据查询两种方式进行查询操作,关闭程序后重新启动 每个设备再次进行2000个随机属性数据写入，完成后在新的数据前提下再进行一轮数据查询，将查询结果写入文件并与原始文件进行比较，做数据正确性验证。记录数据写入时间和查询时间，计算插值效率，计算公式为：写入效率=写入数据总量(数据条数)/写入时间 查询效率=查询数据总量(数据条数)/查询时间 准备数据、写查询结果文件等时间不计算在内 非功能性需求 在实际场景中,内存和磁盘在容量上存在较大差距,因此要求降低索引之间的耦合度,内存索引和磁盘索引能够实现快速切换，在较小内存情况下也可以正常工作。降低数据和索引的耦合度，索引和数据分开存储。持久

7、化产生的文件统一放在与应用程序同一目录下的 Data 文件夹内程序自行建立，对于持久化所产生的文件名称和文件个数不做要求。在接口不变的情况下，不要求但可以在内部使用多线程或异步 io 来提高效率，也可尝试其他方式提升速度。可以增加接口与类。首先考虑效率问题，效率相同的情况下持久化文件越小越好。所有数据文件使用本地磁盘存储,参赛者禁止使用现有数据库产品。其他限制条件：开发 代码采用 c+方式实现，要求在 win7平台上用 vs2008能够编.环境、实验平台、开发语言、数据库、编译器等限制条件 译通过生成32位可执行程序。验证方式：将源文件与测试程序放入 vs2008项目中。要求不做任何改动的情况下可以进行编译，执行 实际测试中会从文件中读取数据，并将查询出的数据写入另一文件并验证 判断依据：写入效率不低于500W/s 查询效率不低于500W/s 计算机资源消耗越小越好，使用内存不能超过500M 原始数据与查询数据需要完全一致 占用磁盘存储空间越少越好 数据持久化功能正确 测试数据或平台：提供给参赛者的测试环境和测试数据。可提供电子档 附工程文件和测试数据。注：测试数据为测试用，不是实际评分的数据。其他要求 参赛者需要提供:1.源代码和可执行程序 2.设计文档,包括算法中的数据结构、索引机制、查询和写入设计、测试结果 3.测试用例 Tags：责任编辑：cnsoft