基于索引的加密數(shù)據(jù)庫(kù)查詢(xún)研究.pdf

1、數(shù)據(jù)加密是保證敏感數(shù)據(jù)保密性的重要手段，如何在加密后的數(shù)據(jù)上進(jìn)行高效查詢(xún)是數(shù)據(jù)庫(kù)研究領(lǐng)域的一項(xiàng)難題。
　　 為提升加密數(shù)據(jù)庫(kù)的查詢(xún)性能，論文設(shè)計(jì)了一種新型的B+樹(shù)密文數(shù)據(jù)庫(kù)索引。通過(guò)用密文塊數(shù)組來(lái)組織加密關(guān)鍵字的方法，使得單個(gè)索引節(jié)點(diǎn)可以容納任意數(shù)量的關(guān)鍵字，從而突破了加密長(zhǎng)度對(duì)索引節(jié)點(diǎn)中關(guān)鍵字字?jǐn)?shù)的限制。在索引節(jié)點(diǎn)中，將關(guān)鍵字與指針?lè)珠_(kāi)加密，可以提高密文塊中關(guān)鍵字的有效存儲(chǔ)率，減少關(guān)鍵字密文塊數(shù)組的長(zhǎng)度，從而可以加速查詢(xún)的命中

2、，減少解密量；為支持范圍查詢(xún)，在葉子節(jié)點(diǎn)中增加前向指針與后向指針，分別指向前面的相鄰葉子節(jié)點(diǎn)與后面的相鄰葉子節(jié)點(diǎn)，使得從一個(gè)葉子節(jié)點(diǎn)就可以方便地找到在它前面或后面的所有葉子節(jié)點(diǎn)。
　　 為加速在關(guān)鍵字密文塊數(shù)組上的查找，論文設(shè)計(jì)了單值查詢(xún)和范圍查詢(xún)的密文塊數(shù)組折半查找算法。單值查詢(xún)的密文塊數(shù)組折半查找算法根據(jù)密文塊數(shù)組的特點(diǎn)，將1個(gè)密文塊視為1個(gè)數(shù)，從而將折半查找的思想應(yīng)用在密文塊數(shù)組上，只是在查詢(xún)過(guò)程中，還須把查詢(xún)值與1個(gè)密文

3、塊的比較，分解成查詢(xún)值與密文塊所含關(guān)鍵字的逐一比較，這樣就解決了傳統(tǒng)折半查找算法只是在一維數(shù)組上進(jìn)行查找的局限，減少了密文塊的解密量。范圍查詢(xún)的密文塊數(shù)組折半查找算法也是將1個(gè)密文塊視為1個(gè)數(shù)，引入折半查找的思想，但是算法在葉子節(jié)點(diǎn)上查找的時(shí)候是查找滿足查詢(xún)條件的邊界關(guān)鍵字，最終的索引查詢(xún)結(jié)果是這個(gè)邊界關(guān)鍵字對(duì)應(yīng)指針及其左邊(或右邊)的指針，以及這個(gè)葉子節(jié)點(diǎn)左邊(或右邊)的所有葉子節(jié)點(diǎn)中的指針?biāo)赶虻挠涗洠ㄟ^(guò)葉子節(jié)點(diǎn)中的前向指針與后向

4、指針，就可以找到滿足查詢(xún)條件的所有葉子節(jié)點(diǎn)，從而在加密數(shù)據(jù)庫(kù)上實(shí)現(xiàn)了含有“＜”、“≤”、“＞”、“≥”等操作符的范圍查詢(xún)。密文塊數(shù)組折半查找算法解決了查詢(xún)值小于密文塊第一個(gè)關(guān)鍵字，大于密文塊最后一個(gè)關(guān)鍵字，介于相鄰加密塊之間以及介于兩相鄰葉子節(jié)點(diǎn)之間情況下的折半查找，解決了關(guān)鍵字在根節(jié)點(diǎn)、分支節(jié)點(diǎn)、葉子節(jié)點(diǎn)等不同節(jié)點(diǎn)中具有不同語(yǔ)義的問(wèn)題。同時(shí)，利用這種索引結(jié)構(gòu)，可以方便地找到整個(gè)被索引字段的最大值、最小值。
　　 仿真實(shí)驗(yàn)證明，