-
Notifications
You must be signed in to change notification settings - Fork 105
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Explain the computation of space complexity #106
Comments
叶子节点是n个, 并且所有节点都有至少2个分支(否则就不需要保留这个节点). 所以叶子的父亲节点数最多是 |
每个节点被查询到之后需要越过源查询key后面几个word; 因为key的最大长度设定为16 KB,所以step最大是2 * 16 KB = 2^15. |
每个word是4bit, 每个字节8bit, 一个字节包含2个word |
“分支信息 + 子节点位置 + Step 信息 + value 总共小于: 16bit * (n-1) + 16bit * (n-1) + 16bit * (n-1) + 4byte * n;” 请问为什么分支信息最大数量是n-1 ? 如果每个内部节点都有两个分支,那么叶节点n, 内部节点n-1, 分支还是2(n-1)呀 |
"对一个存在的key, 我们的索引将返回一个磁盘上的offset, 我们一定可以在这个offset和之后的64KB的磁盘空间上找到这个文件,也就是说, 我们的索引不允许索引过小的文件, 只将文件的位置定位到误差64KB的范围内。" |
只有内部节点有分支信息,叶节点是没有的.
这句话我没太明白哪里不容易理解, 或者你说下你不理解的地方? |
谢谢关于分支信息的解答。 |
会导致非常多的索引的条目.内存可能不够用 |
What document to add
裁剪之后的SlimTrie:
每个节点都有大于1个子节点, 除LeafParent节点之外。
SlimTrie的大小跟key的长度无关. 也就是说任意长度的key的集合都可以使用有限大小的SlimTrie来索引: SlimTrie最多有2n-1个节点: 最多节点是出现在所有inner节点都是二分的时候(空间复杂度为O(n))
//why the most node number of SlimTrie is 2n-1. Could you plase add more comments?
Additional context
The text was updated successfully, but these errors were encountered: