User story: As a developer building on Ceramic, I want a way to store large lists that grow over time but continue to perform well
Goals: Introduce a new StreamType, MutableList, that can store an ever-growing list of items, and provides logarithmic access and iteration for most common access patterns
Additional 'definition of done':
CIP-85 describes an alternative approach that is not being followed in this spec
The data for the list will be represented as a tree structure, where each entry in the list is stored in the leaf nodes. We will provide APIs for sequential access in amortized constant time but worst case logarithmic time (in both forward and reverse insertion order), and for random item access in logarithmic time (all relative to the size of the tree). Existing entries can also be updated (but not deleted).
Each node in the tree will have S children, where S is the Spread Factor. A higher Spread Factor keeps the tree from getting too deep too quickly, but increases the size of each intermediate node slightly. Given the cost of higher spread factors is relatively low, but the benefit potentially quite high, I propose using a Spread Factor of 32 - meaning each non-leaf node will have 32 children. This will make each non-leaf node approximately 1KB in size (assuming IPFS cids are 32 bytes).
Basic structure with S=4: