How to store tree-like data?
I want to implement something like Git, where you have a tree-structure of revisions.
- Every revision has a hash (it's id)
- Every revision has a parent revision (null for the root)
- Every revision may have children revisions (like branching)
Example of such a tree:
I want to be able to fetch a revision as well as it's ancestors up to the root:
Reads are often. Writes are not, and most of them are new revisions (leafs).
For now, I see several ways of doing this:
6 Replies
do you want to be able to both traverse up the tree and down?
I'd likely just do the first approach, index the parentId, and rely on indexing and caching to make everything fast
Just up to the root would be enough.
Could you please clarify what do you mean by caching?
well, for any given node, you'll (1) only walk up the tree once b/c of query caching, and (2) even the individual lookups are likely to be cached. so it will be plenty fast
depends on how deep the tree might be though
I expect it to be under 30 nodes deep. So it should be pretty fast?
yeah
Thanks. I don't know why but it didn't make sense at first.