  In emerging applications such as blockchains and collaborative data
analytics, there are strong demands for data immutability, multi-version
accesses, and tamper-evident controls. This leads to three new index structures
for immutable data, namely Merkle Patricia Trie (MPT), Merkle Bucket Tree
(MBT), and Pattern-Oriented-Split Tree (POS-Tree). Although these structures
have been adopted in real applications, there is no systematic evaluation of
their pros and cons in the literature. This makes it difficult for
practitioners to choose the right index structure for their applications, as
there is only a limited understanding of the characteristics of each index.
  To alleviate the above deficiency, we present a comprehensive analysis of the
existing index structures for immutable data, evaluating both their asymptotic
and empirical performance. Specifically, we show that MPT, MBT, and POS-Tree
are all instances of a recently proposed framework, dubbed \my{Structurally
Invariant and Reusable Indexes (SIRI)}. We propose to evaluate the SIRI
instances based on five essential metrics: their efficiency for four index
operations (i.e., lookup, update, comparison, and merge), as well as their
\my{deduplication ratios} (i.e., the size of the index with deduplication over
the size without deduplication). We establish the worst-case guarantees of each
index in terms of these five metrics, and we experimentally evaluate all
indexes in a large variety of settings. Based on our theoretical and empirical
analysis, we conclude that POS-Tree is a favorable choice for indexing
immutable data.
