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

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

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

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

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