Implementation of a TS Tree for WORM data (i.e. for fact-totem).
Based on the white paper "TS-Trees: A Non-Alterable Search Tree Index for Trustworthy Databases on Write-Once-Read-Many (WORM) Storage∗" by Jian Pei, Man Ki Mag Lau, Philip S. Yu.
Properties of a good index for Trustworthy Databases (WORM):
- When committing a record to WORM storage, the id and path to access must be committed and immutable
- Index must be incrementally maintainable, and scale to large databases
- Data must be searchable using index efficiently
- Cost of index space must be reasonable
- Record must be destroyed once it expires
Goals of TS Trees:
- Maintain virtual sorted list of records
- Relatively balanced data structure
- Provide effective mechanism to detect adversarial changes
Alternatives: General Hashting Trees (GHT), non-ordered and allows probing queries but no range queries
TS-Tree tracks the keys and the path to the value. The Value blobs are stored in blob storage, and the semantics are for Append only operations. I.e. key/paths can be added but not altered or removed.