For the bound on memory usage described in the ART paper, we need to maintain the following invariants.
All Node4's must have at least 2 1 children (let's defer implementing min 2 children since that turns out to be difficult)
All Node16's must have at least 5 children
All Node48's must have at least 17 children
All Node256's must have at least 49 children
max(numChildren, 1) * partialKeyLen >= partialKeyCapacity (for simplicity we'll only require that this one eventually hold)
I think the exact numbers of minimum children could be flexible based on the actual size of our nodes. We can redo the analysis and tinker if we want. We could even come up with a test property asserting bounded memory usage.
For the bound on memory usage described in the ART paper, we need to maintain the following invariants.
- All Node4's must have at least ~~2~~ 1 children (let's defer implementing min 2 children since that turns out to be difficult)
- All Node16's must have at least 5 children
- All Node48's must have at least 17 children
- All Node256's must have at least 49 children
- max(numChildren, 1) * partialKeyLen >= partialKeyCapacity (for simplicity we'll only require that this one eventually hold)
I think the exact numbers of minimum children could be flexible based on the actual size of our nodes. We can redo the analysis and tinker if we want. We could even come up with a test property asserting bounded memory usage.
andrew
added this to the (deleted) project 2024-03-09 00:52:10 +00:00
Blocking a user prevents them from interacting with repositories, such as opening or commenting on pull requests or issues. Learn more about blocking a user.
For the bound on memory usage described in the ART paper, we need to maintain the following invariants.
21 children (let's defer implementing min 2 children since that turns out to be difficult)I think the exact numbers of minimum children could be flexible based on the actual size of our nodes. We can redo the analysis and tinker if we want. We could even come up with a test property asserting bounded memory usage.