TS-trees: A non-alterable search tree index for trustworthy databases on Write-Once-Read-Many (WORM) storage

Abstract

Trustworthy data processing, which ensures the credibility and irrefutability of data, is crucial in many business applications. Recently, the Write-Once-Read-Many (WORM) devices have been used as trustworthy data storage. Nevertheless, how to efficiently retrieve data stored in WORM devices has not been addressed sufficiently and thus remains a grand challenge for large trustworthy databases. In this paper, we describe a trustworthy search tree framework (called TS-tree), which is a simple yet effective nonalterable search tree index for trustworthy databases. It can take the role of B-trees in trustworthy databases to answer various queries including range queries. It is efficient and scalable on large databases. A systematic simulation verifies our design. ©2007 IEEE.