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 larg