基于索引的加密数据库查询研究

《基于索引的加密数据库查询研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南大学硕士学位论文基于索引的加密数据库查询研究姓名：雷春红申请学位级别：硕士专业：计算机软件与理论指导教师：余建桥20100501摘要基于索引的加密数据库查询研究计算机软件与理论专业硕士研究生雷春红指导教师余建桥教授摘要数据加密是保证敏感数据保密性的重要手段，如何在加密后的数据上进行高效查询是数据库研究领域的一项难题。为提升加密数据库的查询性能，论文设计了一种新型的B+树密文数据库索引。通过用密文块数组来组织加密关键字的方法，使得单个索引节点可以容纳任意数量的关键字，从而突破了加密长度对索引节点中关键字字数的限制。在索引节点中，将关键字与指针分

2、开加密，可以提高密文块中关键字的有效存储率，减少关键字密文块数组的长度，从而可以加速查询的命中，减少解密量；为支持范围查询，在叶子节点中增加前向指针与后向指针，分别指向前面的相邻叶子节点与后面的相邻叶子节点，使得从一个叶子节点就可以方便地找到在它前面或后面的所有叶子节点。为加速在关键字密文块数组上的查找，论文设计了单值查询和范围查询的密文块数组折半查找算法。单值查询的密文块数组折半查找算法根据密文块数组的特点，将1个密文块视为1个数，从而将折半查找的思想应用在密文块数组上，只是在查询过程中，还须把查询值与1个密文块的比较，分解成查询值与密文块所含

3、关键字的逐一比较，这样就解决了传统折半查找算法只是在一维数组上进行查找的局限，减少了密文块的解密量。范围查询的密文块数组折半查找算法也是将1个密文块视为1个数，引入折半查找的思想，但是算法在叶子节点上查找的时候是查找满足查询条件的边界关键字，最终的索引查询结果是这个边界关键字对应指针及其左边(或右边)的指针，以及这个叶子节点左边(或右边)的所有叶子节点中的指针所指向的记录，通过叶子节点中的前向指针与后向指针，就可以找到满足查询条件的所有叶子节点，从而在加密数据库上实现了含有“<”、“S’、“>”、‘‘>”等操作符的范围查询。密文块数组折半查找算法

4、解决了查询值小于密文块第一个关键字，大于密文块最后一个关键字，介于相邻加密块之间以及介于两相邻叶子节点之间情况下的折半查找，解决了关键字在根节点、分支节点、叶子节点等不同节点中具有不同语义的问题。同时，利用这种索引结构，可以方便地找到整个被索引字段的最大值、最小值。·西南大学硕十学位论文II仿真实验证明，在索引节点密文块数组上进行折半查找，相比顺序查找，能大大减少解密量，查找更为迅速。关键字：B+树密文索引单值查询范围查询折半查找．AbstractDataencryptionisallimportantmeasuretoensureconfide

5、ntialityofimportantdata．Itisadifficultproblemthathowtoquerytheencryptdatabasedataefficiently．Toenhancequeryperformanceoftheencrypteddatabase，anewtypeofB+treeindexisdesignedforit．Itmakesasingleindexnodecallholdanynumberofkeywordbyusingacipher-textblockarraytoorganizetheencrypt

6、edkeywords，thusbreakingthelimitonnumberofkeywordsintheindexnodebytheencryptionlength．Intheindexnode，keywordsareencryptedandstoredseparatelywithpointers．Sowhatacipher-textblockholdsareallkeywordsorpointers．ThisCallincreasetheeffectiverateofkeywordsinacipher-textblock，reducethe

7、lengthofthekeywordarray．ReducingthelengthofthekeywordarrayCallspeedupthequery,leadtolessdecryption．Tosupporttherangequery,aprior-pointerandanext-pointerareaddedintheleafnode，pointingtotheadjacentfrontleafnodeandthenext锄acentleafnode，SOfromaleafnodeitiseasytofinda11thefrontand

8、allthebackleafnodesofit．Tospeedupsearchonthecipher-textblockarrayofk