基於快取B+樹機制改善加密資料庫查詢效能之研究

Enhancing Query Performance of Encrypted Databases based on a Cached B+Tree

洪家翔(Jia-Shyang Hong)

指導教授 ： 楊正仁

元智大學/資訊學院/資訊工程學系/碩士(2013年)

https://doi.org/10.6838/YZU.2013.00287

摘要

對於資料安全而言，加密資料庫是一個重要的研究方向。然而由於加密資料庫需要進行加解密的運算，因此它的查詢效能會因此降低。過往已經有一些研究討論如何增進加密資料庫的查詢效能，但大都侷限在 B+ 樹的索引結構上。本論文提出一個雜湊快取機制 ECB+ ，利用雜湊函式的快速搜尋特性以及快取機制中的參考區域性，提升對加密資料庫的搜尋效能。在實驗中，ECB+ 實作在一個加密資料庫 SQLCipher 之上。經由 TPC-H 的測試資料庫驗證，ECB+ 在隨機查詢的情況下，可以比過往 CCB+ 機制的查詢效能提升了 11.23-30.62% 。實驗結果顯示，在僅使用有限的額外空間條件下，ECB+ 有效的提升加密資料庫的查詢效能。

關鍵字

加密資料庫 ； 查詢效能 ； 快取B+樹機制 ； 雜湊機制

並列摘要

Database encryption is an important issue for data security. However, one major problem of encrypted databases is the poor query performance. Studies have been conducted to address this issue, but they mainly focus on the B+-tree index structure. This thesis proposes a hash-based caching mechanism called ECB+ to improve the query performance by exploiting the searching effectiveness of the hashing mechanism and the reference locality of the caching mechanism. In the experiments, ECB+ was implemented on an encrypted database system SQLCipher. With the benchmark of the TPC-H databases, ECB+ outperforms a previous work CCB+ in random queries by 11.23-30.62% improvements. The experimental results show that ECB+ can effectively improve the query performance with only additional limited memory space.

並列關鍵字

Encrypted Databases ； Query Performance ； Cached B+ Tree ； Hashing Mechanism

參考文獻

[1] Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, and Yirong Xu, “Order Pre-

serving Encryption for Numeric Data,” in Proceedings of the 2004 ACM SIGMOD

[2] Ahmad Baraani-Dastjerdi, Josef Pieprzyk, and Reihaned Safavi-Naini, “Security in

Databases: A Survey Study,” Department of Computer Science, University of Wol-

[3] Luc Bouganim and Philippe Pucheral, “Chip-Secured Data Access: Confidential