1  研究背景

近年来医院信息系统在全国得到快速推广，医院的人、财、物及病人各种就诊数据都得到信息化管理。然而随着时间推移以及医疗数据需长期稳定保存的特性，大量的病人信息、费用信息、过程型信息和医学文献等集中在各类医疗数据库中。

同时，近年来各地积极建立区域数据中心，用来服务各医疗机构医疗信息互通及医疗资源共享，而数据中心也集中存储了各下属医疗机构上传的大量医疗数据。随着社会保障的逐步完善，社保中心所汇集的参保医疗机构上传数据呈指数增长。如何在庞大的海量数据中快速查询出有效的范围数据被提上研究日程。

范围查询是数据库查询操作的一个重要方面，尤其在医疗数据分析应用中，是使用最频繁的查询之一。如查询给定时间区段的就诊记录、给定体征数据区段的病人信息等。提高数据库查询性能的一个重要手段就是建立合理的索引机制，B+树是在范围查询中被广泛使用的一种索引结构。

随着硬件技术的发展，内存容量越来越大，使数据全部被放入内存成为可能，在数据库索引构建或查询时，不再需要考虑减少磁盘访问次数的问题；同时，由于内存访问速度和处理器的处理速度差异越来越大，内存访问延迟也成为影响索引性能的重要因素。多核技术的出现，提供了更多并行的可能。

主要通过减少树的遍历过程中内存访问延迟对整体性能的影响来达到提高查询性能的目的，如CSS树、CSB+树等，同时利用多核处理器多并发的特点，针对范围查询叶节点遍历时间消耗多的特点，提出一种面向范围查询的并发索引框架（Partition-based Parallel Index Framework，PPIF）。

2  索引的基本结构及算法

2.1 基于数据分组的并行索引框架 范围查询，即给定一个取值范围，选择满足该取值范围的结果。满足查询结果的关键字值越多，遍历叶节点的时间消耗越大，如能有效提高叶节点的遍历性能，将能有效提高查询的整体性能。PPIF框架利用这一特点，将数据进行分组，减少了每个分组索引关键字的数目，使分组内部的范围查询性能提高；分组之间数据相互独立，使分组内部的查询处理可以并行化，通过这种分组并行化方式来提高索引的整体查询性能。

如图1所示，数据被分成多个独立的数据分组，对进入PPIF中的每个值，索引框架为其分配唯一确定的分组，分组的选择策略可根据具体情况具体选择，如基于等价关系等，关键是保证各分组间的数据相互独立。这样，对每个分组，创建各自适用于范围查找的内部索引结构，如B+树，或B+树的变种如CSB+树等。为每个分组创建独立的线程，用于独立执行其内部的插入和范围查询任务。

图1 PPIF基本结构

2.2 PPIF并行范围查询算法 在PPIF的查询流程中，为每个分组分配一个独立的分组查询线程，PPIF并行的范围查询算法流程包括两部分：任务分发线程和分组查询线程，如图2所示。

图2 PPIF并行查询算法

任务分发线程：当有新的查询，任务分发线程将该查询分发给所有分组查询线程，并通知所有分组查询线程任务到达，然后等待直到所有分组查询线程完成为止。

分组查询线程：当分组查询线程接收到任务分发线程的任务到达通知后，分组线程开始进行分组查询操作，对每个分组查询线程，按照各自的分组索引范围查找算法完成范围查找操作之后返回结果，并通知任务分发线程当前分组完成查询，同时该组查询线程进入等待状态，等待下一次的查询任务到来。

和普通索引相比，在PPIF中的精确查找和删除过程的消耗包括分组内部操作及线程同步的消耗。

3  实验及结果分析

通过实验比较PPIF结构和普通索引之间的性能，为不失一般性，选择B+树作为PPIF每个分组内部的索引结构，在实验中比较PPIF B+结构并行范围查询和B+树范围查询性能，并分析不同的分组数目、不同的查询范围对查询性能提高程度的影响。

实验机器的系统为Windows 7/64位，所有的算法用C++实现，编译环境为visual studio 10 win64。实验选择在两个不同的硬件环境进行，两台机器的硬件指标如表1所示。

表1 实验硬件参数

实验模拟了1-100 000 000之间30 000 000个互不相同的整数值，同时模拟了不同查询范围的查询条件，查询范围包括10000、20000、50000、80000、100000、150000、200000，每个查询范围包含100000个查询条件，查询条件随机生成。机器A分别在B+tree、2-PPIF B+、3-PPIF B+、4-PPIF B+、6-PPIF B+、8-PPIF B+中完成，机器B分别在B+tree、2-PPIF B+、4-PPIF B+、8-PPIF B+、12-PPIF B+、16-PPIF B+、18-PPIF B+中完成，并累计每个范围100000次查询的总时间。每个实验进行10次，取平均值作为实验结果，得到实验结果如图3、图4所示。

图3 机器A查询性能比较

图4 机器B查询性能比较

如图3所示，在PPIF结构中，对范围查询的查询性能的提高，主要是通过对数据的分组，并行处理符合条件的数据来达到性能的提高。但是，并行处理带来了一些额外的时间消耗，如线程同步等。当符合条件的范围较小，通过并行带来的性能优化小于并行处理需要的额外时间消耗时，查询时间要大于基本的B+树的查询时间。

利用PPIF并行结构进行并行查询时，一般线程数越多，查询性能越好，但分组数越多，并行线程越多，线程同步开销和缓存缺失越多，当并行线程增多带来的性能提升小于增加的缓存缺失和线程同步等时间开销，查询性能则略有降低。由图3可以看到，当线程数大于等于4时，查询时CPU的占用率已超过95%，因而分组数的增加不能带来性能提升；同样，在图4中，查询范围大于100000时，18-PPIF B+的性能低于16-PPIF B+的性能，这是在CPU利用率超过极限时，线程的并行处理带来性能提升很小，同时并行线程增多，带来更多的线程同步、缓存冲突等时间消耗，导致查询性能降低。 打印腕带

4  总结与展望

面向医疗数据查询中的范围查询，通过分析范围查询中主要的查询消耗，利用多核处理器的并行处理特点，提出基于数据分组的并行的索引框架PPIF。实验表明，在PPIF框架中，基于一定CPU处理能力的前提下，分组的并行处理有效提高了索引的批量更新性能及范围查询性能，将其应用于医疗海量数据范围查询，可以满足各种医疗实时查询需求。在接下来的研究中，将进一步细化分析并行处理的消耗时间的主要构成，以提高并行范围查询的性能；同时考虑在混合任务（多个更新任务和查询任务同时到达）下，并行索引框架的并发访问控制及任务调度问题，进一步提高更复杂的海量医疗数据的范围查询性能。

（来源：节选自《中国数字医学》杂志2016年第9期 作者：晏庆 单位：91469部队 ；作者：吕雪峰 单位： 全军后勤信息中心勤务三室 ；作者：孙晓玮 冷金昌 单位：解放军总医院第一附属医院信息科）