Delveroff
Delveroff4mo ago

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:
A -> B -> C -> D
\-> C2
A -> B -> C -> D
\-> C2
I want to be able to fetch a revision as well as it's ancestors up to the root:
await findAncestors('D') // A, B, C, D
await findAncestors('C') // A, B, C
await findAncestors('C2') // A, B, C2
await findAncestors('D') // A, B, C, D
await findAncestors('C') // A, B, C
await findAncestors('C2') // A, B, C2
Reads are often. Writes are not, and most of them are new revisions (leafs). For now, I see several ways of doing this:
type Revision = {
parentId: DocId<'revisions'> // need recursive query? what about indexing?
}
type Revision = {
parentId: DocId<'revisions'> // need recursive query? what about indexing?
}
type Revision = {
children: Array<DocId<'revisions'>> // what about cascade deletes? also indexing
}
type Revision = {
children: Array<DocId<'revisions'>> // what about cascade deletes? also indexing
}
type Revision = {
path: Array<DocId<'revisions'>> // seems attractive if indexing by the array
}
type Revision = {
path: Array<DocId<'revisions'>> // seems attractive if indexing by the array
}
6 Replies
jamwt
jamwt4mo ago
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
Delveroff
DelveroffOP4mo ago
Just up to the root would be enough. Could you please clarify what do you mean by caching?
jamwt
jamwt4mo ago
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
Delveroff
DelveroffOP4mo ago
I expect it to be under 30 nodes deep. So it should be pretty fast?
jamwt
jamwt4mo ago
yeah
Delveroff
DelveroffOP4mo ago
Thanks. I don't know why but it didn't make sense at first.

Did you find this page helpful?