Anti-Persistence on Persistent Storage
Michael A. Bender, Jonathan W. Berry, Rob Johnson, Thomas M Kroeger, Samuel McCauley, Cynthia A. Phillips, Bertrand Simon, Shikha Singh, David Zage · 2016
We present history-independent alternatives to a B-tree, the primary indexing data structure used in databases. A data structure is history independent (HI) if it is impossible to deduce any information by examining the bit representation of the data structure that is not already available through the API. We show how to build a history-independent cache-oblivious B-tree and a history-independent external-memory skip list. One of the main contributions is a data structure we build on the way---a history-independent packed-memory array (PMA). The PMA supports efficient range queries, one of the most important operations for answering database queries.