第３８卷第４期 计算机应用与软件
Ｖｏｌ ３８Ｎｏ．４２０２１年４月
ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ
Ａｐｒ．２０２１
王 莱 周腾达 王正飞 洪佳明
（广州中医药大学医学信息工程学院 广东广州５１０００６）
收稿日期：
２０１９－０７－１６。广东省自然科学基金项目（２０１５Ａ０３０３１０３１２）；广州中医药大学人文社会科学“远志”项目（ＳＫＹＺ１６０４）。王莱，硕士生，主研领域：中医药信息化。周腾达，本科生。王正飞，副教授。洪佳明，讲师。
摘 要 电子病历包含病人的隐私信息，如何在保密情况下进行电子病历内容搜索是医院电子病历数
据有效利用的难点。针对电子病历密文搜索，提出一种基于布隆过滤器（ＢＦ）和Ｂ＋树的快速搜索方法。该技术对电子病历建立Ｂ
Ｆ，按照倒排索引方式组织起来并建立Ｂ＋树，能够支持在不泄露用户搜索关键词的前提下，对电子病历密文直接进行查询，安全级别达到ＩＮＤ ＣＫＡ级别。实验结果表明：由于使用ＢＦ与Ｂ＋树结构，空间过滤特性高，无须解密即可达９９％的过滤效率，查询效率高，且支持布尔查询，有效促进加密电子病历数据的应用。关键词 电子病历 布隆过滤器 Ｂ＋树 倒排索引 密文查询 中图分类号 ＴＰ３ 文献标志码 Ａ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００ ３８６ｘ．２０２１．０４．０４５
ＳＥＡＲＣＨＯＮＥＮＣＲＹＰＴＥＤＥＬＥＣＴＲＯＮＩＣＭＥＤＩＣＡＬＲＥＣＯＲＤＳＵＳＩＮＧＩＮＶＥＲＴＥＤＩＮＤＥＸＢＡＳＥＤＯＮＢＬＯＯＭＦＩＬＴＥＲＡＮＤＢ＋ＴＲＥＥ
ＷａｎｇＬａｉ ＺｈｏｕＴｅｎｇｄａ ＷａｎｇＺｈｅｎｇｆｅｉ
ＨｏｎｇＪｉａｍｉｎｇ
（ＳｃｈｏｏｌｏｆＭｅｄｉｃａｌＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＧｕａｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙｏｆＣｈｉｎｅｓｅＭｅｄｉｃｉｎｅ，Ｇｕａｎｇｚｈｏｕ５１０
００６，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ Ｔｈｅｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄｃｏｎｔａｉｎｓｔｈｅｐａｔｉｅｎｔｓ ｐｒｉｖａｃｙｉｎｆｏｒｍａｔｉｏｎ．Ｉｔｉｓｄｉｆｆｉｃｕｌｔｔｏｓｅａｒｃｈｔｈｅｃｏｎｔｅｎｔｓｏｆｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄｓｉｎａｃｏｎｆｉｄｅｎｔｉａｌｓｉｔｕａｔｉｏｎｏｆｔｈｅｅｆｆｅｃｔｉｖｅｕｔｉｌｉｚａｔｉｏｎｏｆｔｈｅｈｏｓｐｉｔａｌ ｓｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄｄａｔａ．Ａｉｍｉｎｇａｔｃｉｐｈｅｒｔｅｘｔｓｅａｒｃｈｏｆｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄｓ，ａｆａｓｔｓｅａｒｃｈｍｅｔｈｏｄｂａｓｅｄｏｎｂｌｏｏｍｆｉｌｔｅｒ（ＢＦ）ａｎｄＢ＋ｔｒｅｅｉｓｐｒｏｐｏｓｅｄ．ＴｈｅＢＦｏｆｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄｗａｓｅｓｔａｂｌｉｓｈｅｄ，ａｎｄＢ＋ｔｒｅｅｗａｓｅｓｔａｂｌｉｓｈｅｄａｃｃｏｒｄｉｎｇｔｏｉｎｖｅｒｔｅｄｉｎｄｅｘｍｏｄｅ．Ｉｔｃｏｕｌｄｓｕｐｐｏｒｔｄｉｒｅｃｔｑｕｅｒｙｏｆｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄｃｉｐｈｅｒｔｅｘｔｗｉｔｈｏｕｔｄｉｓｃｌｏｓｉｎｇｕｓｅｒｓ ｓｅａｒｃｈｋｅｙｗｏｒｄｓ，ａｎｄｔｈｅｓｅｃｕｒｉｔｙｌｅｖｅｌｒｅａｃｈｅｄＩＮＤ ＣＫＡｌｅｖｅｌ．ＴｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｄｕｅｔｏｔｈｅｕｓｅｏｆＢＦａｎｄＢ＋ｔｒｅｅｓｔｒｕｃｔｕｒｅ，ｔｈｅｓｐａｔｉａｌｆｉｌｔｅｒｉｎｇｃｈａｒａｃｔｅｒｉｓｔｉ
ｃｓａｒｅｈｉｇｈ，ｔｈｅｆｉｌｔｅｒｉｎｇｅｆｆｉｃｉｅｎｃｙｃａｎｒｅａｃｈ９９％ｗｉｔｈｏｕｔｄｅｃｒｙｐｔｉｏｎ，ａｎｄｔｈｅｑｕｅｒｙｅｆｆｉｃｉｅｎｃｙｉｓｈｉｇｈ．ＩｔｓｕｐｐｏｒｔｓＢｏｏｌｅａｎｑｕｅｒｙ，ｗｈｉｃｈｅｆｆｅｃｔｉｖｅｌｙｐｒｏｍｏｔｅｓｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｅｎｃｒｙｐｔｅｄｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄｄａｔａ．
Ｋｅｙｗｏｒｄｓ Ｅｌｅｃｔｒｏｎｉｃｍｅｄｉｃａｌｒｅｃｏｒｄ Ｂｌｏｏｍｆｉｌｔｅｒ（ＢＦ） Ｂ＋ｔｒｅｅ ＩｎｖｅｒｔｅｄＩｎｄｅｘ Ｃｉｐｈｅｒｔｅｘｔｑｕｅｒｙ
０ 引 言
电子病历中包含了许多隐私信息，包括病人的个人信息、性别、年龄、身份证号等，身体情况中单是病史就包括了既往史、现病史、月经史、婚育史等多项内容。如何保护这些隐私信息在云服务（或者外包）环境中
不被泄露变得非常重要［
１］，进一步地，我们还常常需要进行信息检索。
当前大数据发展如火如荼，电子病历数据越来越
冗杂，医疗机构信息化建设必须加快。２０１９年１月，国务院办公厅下发《关于加强三级公立医院绩效考核工作的意见》（国办发〔２０１９〕４号），要求三级公立医院要加强以电子病历为核心的医院信息化建设，将“电子病历应用功能水平分级”指标列为国家监测指标。按照相关规定，２０１９年８月底前，各地卫健委须组织三级公立医院完成电子病历的编码和术语转换工作，将全面启用统一的疾病分类编码、手术操作编码、
第４期 王莱，等：基于布隆过滤器和Ｂ＋树构建倒排索引的电子病历密文搜索２７７
医学名词术语。
加密是电子病历数据的基本要求，有效搜索则是利用与处理电子病历数据的基础技术。但由于隐私信息加密后失去了原有语义，如何对密文进行准确和快速查询成为关键问题。许多研究人员都对密文查询进
了研究，Ｓｏｎｇ等［２］
首次提出了对密文进行搜索，用户
采用对称加密算法完成加密后发送给服务器，查询时，用户采用哈希函数建立陷门（ｔｒａｐｄｏｏｒ）并发送给服务器，服务器根据陷门完成搜索后，返回密文给用户。与Ｓｏｎｇ等类似，Ｂｏｎｅ
ｈ利用哈希函数和双线性对映射生成密文，用户关键词映射为搜索凭证发送给服务器完成对密文的搜索，该方法为非确定性加密，服务器端无法根据密文判断其中包含的关键词。但这些方法都需
要对所有文档进行搜索，搜索效率低下。Ｗａｎｇ等［３］根
据关键词的出现频率先进行排序，实现密文的搜索，但
排序会在一定程度上影响安全性［
４］
。针对密文搜索效率低下的问题，Ｇｏｈ［５］
提出一种
基于布隆过滤的ｚ
ｉｎｄｅｘ方法，该方法建立在布隆过滤器的基础上，为每个文档增加对应的ＢＦ数据结构。该文定义和实施了四个函数：Ｋｅｙｇｅｎ（ｓ），Ｔｒａｐｄｏｏｒ（Ｋｐｒｉｖ，ｗ），ＢｕｉｌｄＩｎｄｅｘ（Ｄ，Ｋｐｒｉｖ），ＳｅａｒｃｈＩｎｄｅｘ（Ｔｗ，ＩＤ）。其中：
Ｋｅｙｇｅｎ（）用来生成包含多个子密钥的主密钥；Ｔｒａｐｄｏｏｒ（）用来生成关键词对应的陷门；ＢｕｉｌｄＩｎｄｅｘ（）用来为每个文档构建索引；ＳｅａｒｃｈＩｎｄｅｘ（）用来根据用户提交的陷门完成对加密文档查询。该方法的主要优点是能够利用哈希函数快速计算的特点，迅速从密文中直接查询到匹配的文档。但是该方法需要对文档中所有布隆过滤器进行遍历，才能搜索到匹配的文档，极大地影响了系统的性能，特别是在大规模数据处理场景中不适用。
Ｄｅｍｅｒｔｚｉｓ等［６］对于ＳＥ（ＳｅａｒｃｈａｂｌｅＥｎｃｒｙｐｔｉｏｎ）领
域十分关注，提出了两种在保证安全性的前提下提升工作效率的方案，其具有可调整局域性和线性空间，提升了读取效率和减少了端到端的搜索时间，并可以调优以实现空间、读取效率、位置、并行性和通信开销之
间的权衡。Ｄ
ｅｍｅｒｔｚｉｓ等［７］
试图在效率和安全性之间进行权衡的另一个方案则基于可搜索对称加密（ＳＳＥ）技术，主要用于关键字搜索，使用了树状索引的范围覆盖技术将范围搜索简化为多关键词搜索。
本文在ｚ
ｉｎｄｅｘ的基础上对布隆过滤器ＢＦ进行改进，把布隆过滤器组织成倒排文件，并建立Ｂ＋树，充
分利用了布隆过滤器的过滤效率高［８］
和倒排索引的全
文快速查询特点，从而提高电子病历密文查询性能。
１ 电子病历密文搜索模型
为了支持对加密电子病历的密文查询，设计了电子病历密文搜索模型，如图１所示。数据拥有者根据电子病历文档中所包含的关键词，为其建立索引，然后把加密后的电子病历和其对应索引提交给云服务器；用户查询电子病历时，提交陷门（加密后的关键词）给云服务器，云服务器根据陷门在索引中进行查询，在不解密情况下到匹配的电子病历密文，并把密文返回给用户，
用户收到密文后再解密。
图１ 电子病历密文搜索模型
这种模型很好地保护了用户隐私信息安全。一方面，由于用户只是提交了陷门，用户的查询关键词不会暴露给云服务器，所以云服务器无法直接获得用户的查询请求。另一方面，云服务器在查询过程中，使用密文索引直接进行查询，无须对密文电子病历进行解密，更好地保护了密文电子病历隐私信息的安全。在该模型中，为进一步提高对索引检索的效率，本文把布隆过滤器组织为Ｂ＋树，检索效率从原来的Ｏ（ｎ）提高到Ｏ（ｌｏｇｍｎ
）。 ２ 方法设计
２．１ 布隆过滤器创建
布隆过滤器（ＢｌｏｏｍＦｉｌｔｅｒ，ＢＦ）起源于１９７０年，由ＢｕｒｔｏｎＢｌｏｏｍ首次提出，是一种高时空效率的数据结构，由一个一定长度（比如１２８ｂｉｔ位）的二进制向量和
一组相互独立的哈希函数组成［９］
。布隆过滤器可以用
来检查一个元素是否出现在一个数据集合中，具有很好的过滤效果。
对于特定关键词Ｗ，建立布隆过滤器过程如下：（
１）使用密钥生成算法Ｋｅｙｇｅｎ（ｓ）：给定一个安全参数ｓ，生成主密钥Ｋｐｒｉｖ＝（ｋ１，ｋ２，…，ｋｒ
）←Ｒ｛０，１｝ｓｒ
，其中主密钥包含ｒ个子密钥，每个子密钥的长度为Ｓｂｉｔ位。
２７８
计算机应用与软件
２０２１年
（２）使用陷门生成算法Ｔｒａｐｄｏｏｒ（Ｋｐｒｉｖ
，ｗ）：给定主密钥Ｋｐｒｉｖ和查询关键词ｗ，生成陷门Ｔｗ＝（ｆ（ｗ，ｋ１
），ｆ（ｗ，ｋ２），…，ｆ（ｗ，ｋｒ
））∈｛０，１｝ｓｒ，其中ｆ是伪随机函数，本文使用哈希函数ＨＭＡＣ ＳＨＡ１作为伪随机函数：
｛０，１｝ ×｛０，１｝１６０→｛
０，１｝１６０，允许处理任意长度关键词。对于每个关键词ｗ，进行ｒ次哈希处理，每次使用一个子密钥ｋｒ，每次会产生一个陷门值。产生的陷门要保存好，因为在后续的索引构建和用户查询过程中将会继续使用。
例：电子病历中的主诉文档包含关键词“糖尿病”，假定布隆过滤器长度为１２８ｂｉｔ。（１）生成主密钥Ｋｐｒｉｖ＝（ｋ１，ｋ２，ｋ３，ｋ４）；（２）计算“糖尿病”的陷门和编码词，ｘ１＝ｆ（“糖尿病”，ｋ１），ｘ２＝ｆ（“糖尿病”，ｋ２），ｘ３＝ｆ（“糖尿病”，ｋ３），ｘ４＝ｆ（“糖尿
病”，ｋ４）），ｃ１＝ｆ（Ｄｉｄ‖ｘ１），ｃ２＝ｆ（Ｄｉｄ‖ｘ１），ｃ３＝ｆ（Ｄｉｄ‖ｘ１），ｃ４＝ｆ（Ｄｉｄ‖ｘ４）；（３）对编码词ｃ１，ｃ２，…，ｃ４进行哈希计算ｐｒ＝Ｈｒ（ｃｒ），得到ｐ１＝７９，ｐ２＝２５，ｐ３＝４８，ｐ４＝１０３，则布隆过滤器相应的位置“１”，如图２所示，在布隆过滤器的第２５、４８、７９和１０３位置为１，其余为０
。
图２ 布隆过滤器
２．２ 基于布隆过滤器的倒排索引创建（ＢＦ＿ＩＩ）
为电子病历中所有的关键词建立好布隆过滤器后，需要构建基于布隆过滤器的倒排索引，如图３虚线部分所示。倒排文件中包含倒排列表和词典两部分。倒排列表包含某一关键词的所有文档的地址集合，
与传统倒排文件相同；词典包含ＢＦｉ和指针ｐｉ，词典中用ＢＦｉ
代替了传统的关键词。
图３ 基于Ｂ＋树的倒排索引构建
需要注意的是，本文中ＢＦ与ｚ ｉｎｄｅｘ创建ＢＦ有所区别，
ｚ ｉｎｄｅｘ为每份电子病历建立布隆过滤器，而本文通过分词器从电子病历提取关键词，然后为每个关键词构建布隆过滤器，并代替倒排索引中的词典。在建立布隆过滤器的过程中，把包含同一个关键词的电
子病历放到同一个集合中。如果多份电子病历中都包含了关键词“高血糖”，那么就将这些电子病历的地址放到同一个集合中，其他的关键词重复上述步骤，最后得到本文的倒排索引。此外，可将ＢＦ按照频次高低进行排序，进一步提高查询效率。
将布隆过滤器与倒排索引结合起来，一方面充分利用了布隆过滤器的高空间过滤性和倒排索引的高效文本搜索性能；另一方面将明文的关键词转换为布隆过滤器，还能保护用户查询请求的安全和云服务器中数据的安全。
２．３ 基于Ｂ＋树和布隆过滤器的倒排索引
（Ｂ＿ＢＦ＿ＩＩ）
利用布隆过滤器查询时，由于词典中的词表ＢＦ是有序的，可以采用二分查询算法，查询代价为Ｏ（ｌｏｇ２
ｎ），但是在大数据环境中，倒排索引空间开销大，内存难以存放，将极大降低系统查询性能［１０］
。因
此，在ＢＦ＿ＩＩ的基础上，提出一种改进的基于Ｂ＋树的倒排文件（
Ｂ＿ＢＦ＿ＩＩ），利用Ｂ＋树快速查询的特点，为倒排文件中的词典建立Ｂ＋树索引，如图３左部所示。在Ｂ＋创建时，把词典中的ＢＦ作为叶节点，然后逐步建立中间节点，直至根节点。
２．４ 电子病历密文查询算法
把加密的电子病历和倒排索引以及Ｂ＋索引发送给云服务器存储。查询时，用户提交陷门，首先对Ｂ＋检索，快速定位到倒排索引中词表，然后到布隆过滤器对密文直接筛选。
对加密数据的查询，分两步进行：（１）客户端生成陷门Ｔｗ，对Ｂ＋树进行查询，到满足查询条件的叶节点，获得相应电子病历的ｉｄ，根据ｉｄ读取对应的加密电子病历文档并传输至客户端；（２）客户端解密获得明文电子病历。
算法１ 基于ＢＦ和Ｂ＋树加密电子病历查询
输入：搜索的关键词Ｗｉ，Ｄｉｄ（电子病历编号）。输出：密文电子病历。
１．用户计算陷门Ｔｗ＝Ｔｒａｐｄｏｏｒ（Ｋｐｒｉｖ，ｗｉ）＝（ｘ１，ｘ２，…ｘｒ），并发送给服务器。
２．服务器接收到陷门Ｔｗ
。（１）（ｃ１＝ｆ（Ｄｉｄ‖ｘ１），（ｃ２＝ｆ（Ｄｉｄ‖ｘ２），…，ｃｒ＝ｆ（Ｄｉｄ‖ｘｒ））∈｛０，１｝ｓｒ
。（２）计算编码词的位置，选取ｒ个哈希函数Ｈ１，Ｈ２，…，Ｈｒ，计算ｐ１＝Ｈ１（ｃ１），ｐ２＝Ｈ２（ｃ２），…，ｐｒ＝Ｈｒ（ｃｒ
）。（３）把布隆过滤器ＢＦ中ｐ１，ｐ２，…，ｐｔ的位置上修改为１，没有修改过的仍为０，得到该关键词的布隆过滤器。
（４）查询Ｂ＋树，从根节点开始，直至叶节点。如果到满足条件的叶节点（倒排索引中的词条），继续步骤３，否则停止搜索，
第４期 王莱，等：基于布隆过滤器和Ｂ＋树构建倒排索引的电子病历密文搜索２７９
返回未到密文电子病历信息。
３．服务器根据倒排索引中的词条所对应的指针Ｐ
ｉ
，搜索到倒排文档的地址集合，然后返回用户密文电子病历。
４．用户解密，获得明文电子病历。
３ 系统分析
３．１ 安全性分析
（１）服务器安全性。服务器存储了电子病历密文和索引两部分，前者采用了加密算法（如ＡＥＳ、ＤＥＳ）进行加密以保证其安全性，能够抵抗选择明文攻击，本文不作讨论。后者是根据前者的关键词经过一系列转换得到，转换过程主要使用了哈希函数保证其安全性。如图３所示，索引结构中包含了ＢＦ、倒排文件和Ｂ＋树，由于倒排索引和Ｂ＋都是建立在ＢＦ的基础上，安全的关键在于ＢＦ上。在ＢＦ的构建过程中，首先通过
用户的安全参数ｓ动态生成ｒ个密钥ｋ
ｉ
，只要用户安全参数ｓ不泄露，即使攻击服务器端获得用户的身份信息，也无法获得密钥。其次在产生陷门时，采用了伪随机函数（ＨＭＡＣ ＳＨＡ１），对于布隆过滤器中的每个词条进行了ｒ次哈希处理，能够抵抗选择明文攻击（ＡｄａｐｔｉｖｅＣｈｏｓｅｎＫｅｙｗｏｒｄＡｔｔａｃｋ，ＩＮＤ ＣＫＡ）［１１］。在倒排文件中，ＢＦ与地址ｐ连接成为词典，ＢＦ是有序的，但并不会给攻击者带来任何机会，因为从ＢＦ的构建过程中可以发现，ＢＦ有序，但关键词的顺序被打乱，攻击者无法从ＢＦ的有序信息得到关键词的顺序关系。类似地，Ｂ＋树也是根据ＢＦ的顺序来构建，攻击者也无法进行选择明文攻击［１２］。
（２）用户端安全性。首先，用户查询电子病历时，向服务器发送陷门，而不是关键词，保证了用户查询使用的关键词不被服务器知道。其次，服务器返回电子病历密文，很好地保护了用户查询结果的安全。３．２ 正确性分析
把加密的电子病历和倒排索引以及Ｂ＋索引发送给云服务器存储。查询时，用户提交陷门，首先对Ｂ＋检索，快速定位到倒排索引中词表，然后到布隆过滤器对密文直接筛选。利用布隆过滤器查询电子病历密文时，不会遗漏任何包含该关键词的电子病历。根据
ＢｕｉｌｄＩｎｄｅｘ（Ｄ，Ｋ
ｐｒｉｖ
），每个关键词都会在布隆过滤对应的ｒ个位上置１。查询时，根据用户提交陷门再重复相同计算，必定也是在相同的ｒ个位上置１，所以只要电子病历包含该关键词，绝对不会遗漏。
但是，布隆过滤器置１时，由于为不同关键词建立索引时，同一个位置可能会重复置１，这样可能产生假阳性（ＦａｌｓｅＰｏｓｉｔｉｖｅｓ）。假阳性概率为：
１－１－
１
[]
ｍ
[]ｋｍｋ≈（１－ｅ－ｋｎ／ｍ）ｋ（１）式中：ｍ是过滤器大小（ｂｉｔ）；ｎ是关键词个数；ｋ是哈希函数个数。可以观察到，随着过滤器位数ｍ增加，假阳性概率下降；随着关键词个数ｎ的增加，假阳性概率上升。
３．３ 性能分析
在电子病历文档中，常用医学专业词汇关键词个数１０００个左右，假设使用８个哈希函数，那么布隆数组大小为２１３＝８１９２ｂｉｔ，假阳率能够控制在０．０１即１／１００之内，这样的空间过滤效果能够满足密文电子病历搜索需求。
对于未能过滤掉的伪文档，常见的处理方法是发送给用户，用户解密后发现文档不符合要求再舍弃。当然，发送给用户的密文都需要与访问控制措施结合起来，用户有权限才能获得相关的密文。
作为树形的数据结构的Ｂ＋树能够多路查，具有能够保持数据的稳定有序的特点，有良好的查询效率［１３］，因此Ｂ＋树被广泛应用于数据库和操作系统的文件系统中，如此广泛的应用足以体现出Ｂ＋树查询等方面的优势。本文使用Ｂ＋树将倒排文件组织成ＢＩＦ，充分挖掘Ｂ＋树的查询优势。
４ 实 验
在实验中，比较了倒排索引（ＩＩ）、基于布隆过滤器的倒排索引（ＢＦ＿ＩＩ）、基于Ｂ＋树和ＢＦ的倒排索引（Ｂ＿ＢＦ＿ＩＩ）方法在创建时的空间代价和查询的时间代价。实验中使用的关键词是从常用临床医学术语中获取，分成１６３０和５２９５两组。每次实验做１０次，取其平均值作为最后实验分析数据。实验中使用的哈希算法为ＨＭＡＣ ＳＨＡ１，实验环境为Ｗｉｎｄｏｗｓ１０操作系统，Ｐ４２．８ＧＨｚ的ＣＰＵ，８ＧＢ的内存。
４．１ 构建索引的空间代价
在实验中，对三种不同索引的空间大小进行比较。如图４所示，（ａ）和（ｂ）比较了关键词个数分别为１６３０和５２９５时三种索引的空间大小。从实验结果可以得出：布隆过滤器大小由８ｂｉｔ逐渐增加至１２８ｂｉｔ时，ＢＦ＿ＩＩ比ＩＩ的空间稍微减少，这是由于ＢＦ过滤器采用位图表示，比关键词所占存储空间相应少一些。而Ｂ＿ＢＦ＿ＩＩ相对另外两种索引空间稍微增加，这主要是因为Ｂ＿ＢＦ＿ＩＩ在ＢＦ＿ＩＩ基础上增加了二级索引Ｂ＋，空间相应地增加了一些。
２８０
计算机应用与软件
２０２１
年
（ａ）关键词个数为１６３
０
（ｂ）关键词个数为５２９５图４ 索引的存储空间
４．２ 查询的时间代价
用户查询代价是衡量系统性能的最重要指标，尽量减少查询和验证时间是本文研究的一个重要目的。在这个实验中，用户查数据时，采用了单关键词查询和多关键词查询两种方式，例如：单关键词查询疾病为“糖尿病”，多关键词查询疾病为“糖尿病”和“血脂高”。如图５所示，通过单关键词查询的实验结果对比可以得出，ＢＦ＿ＩＩ比ＩＩ的性能稍优，而在ＢＦ的位数增加时性能优势稍微有所减少，这是因为在ＢＦ位数小时进行比较的位数少，比关键词的直接比较要稍微快一点，所以随着ＢＦ位数增加，ＢＦ＿ＩＩ的优势就会有所减弱。而Ｂ＿ＢＦ＿ＩＩ在布隆过滤器位数较少时查询代价比ＢＦ＿ＩＩ的要高出许多，但是随着ＢＦ位数的增加Ｂ＿ＢＦ＿ＩＩ的查询性能体现出很大的优势。所以当ＢＦ位数比较大时，Ｂ＿ＢＦ＿ＩＩ
的查询代价有明显优势。
（ａ）关键词个数为１６３
０
（ｂ）关键词个数为５２９５图５ 单关键词用户查询代价
多关键词查询的实验结果对比如图６所示，实验结果与单关键词查询结果相似，在ＢＦ位数较少时，
ＩＩ与ＢＦ＿ＩＩ的性能相近，但ＢＦ＿ＩＩ的略优，此时两者都比Ｂ＿ＢＦ＿ＩＩ的性能好。但当ＢＦ位数较大时，Ｂ＿ＢＦ＿ＩＩ的
查询性能体现出明显优势。
（ａ）关键词个数为１６３
０
（ｂ）关键词个数为５２９５图６ 多关键词用户验证代价
４．３ 与ｚ ｉｎｄｅｘ查询时间代价对比
本文基于ｚ ｉｎｄｅｘ对可搜索密文技术进行相应改进。上述实验结果还没有对比本文技术与ｚ ｉｎｄｅｘ查询方面的性能。如图７所示，
就是本文所说的四种索引之间的查询代价对比图。该实验中ＢＦ的大小为１２８ｂｉｔ，从实验结果对比可知前三者的查询性能都比ｚ ｉｎｄｅｘ有着明显的优势。根据上文的叙述前三者都是倒排索引，而ｚ ｉｎｄｅｘ是正排索引，所以从实验结果可以看出，
倒排索引在查询性能上拥有良好的优势。
图７ 与ｚ ｉｎｄｅｘ查询代价的对比
５ 结 语
本文中主要讨论如何设计索引，用户通过对索引的查询就能获得密文，而不需要解密，针对现有可搜索密文技术的一些缺陷进行改进，主要采用了基于ＢＦ的倒排索引与Ｂ＋树结合的方法，提高了电子病历的
密文查询效率，还能支持布尔查询进行“与”“或”“非”
（下转第３３３页）
