Explain the computation of space complexity about slim HOT 8 CLOSED

叶子节点是n个, 并且所有节点都有至少2个分支(否则就不需要保留这个节点). 所以叶子的父亲节点数最多是n/2个. 然后爷爷节点数同理是n/4. 然后一直向上, 累加起来就是2n-1了

from slim.

每个节点被查询到之后需要越过源查询key后面几个word； 因为key的最大长度设定为16 KB，所以step最大是2 * 16 KB = 2^15.
请问为什么16KB乘以2？

from slim.

每个word是4bit, 每个字节8bit, 一个字节包含2个word

from slim.

“分支信息 + 子节点位置 + Step 信息 + value

总共小于: 16bit * (n-1) + 16bit * (n-1) + 16bit * (n-1) + 4byte * n；”

请问为什么分支信息最大数量是n-1 ? 如果每个内部节点都有两个分支，那么叶节点n, 内部节点n-1, 分支还是2(n-1)呀

from slim.

"对一个存在的key, 我们的索引将返回一个磁盘上的offset, 我们一定可以在这个offset和之后的64KB的磁盘空间上找到这个文件，也就是说, 我们的索引不允许索引过小的文件, 只将文件的位置定位到误差64KB的范围内。"
请问这段话怎么理解。

from slim.

请问为什么分支信息最大数量是n-1 ? 如果每个内部节点都有两个分支，那么叶节点n, 内部节点n-1, 分支还是2(n-1)呀

只有内部节点有分支信息,叶节点是没有的.

"对一个存在的key, 我们的索引将返回一个磁盘上的offset, 我们一定可以在这个offset和之后的64KB的磁盘空间上找到这个文件，也就是说, 我们的索引不允许索引过小的文件, 只将文件的位置定位到误差64KB的范围内。"
请问这段话怎么理解。

这句话我没太明白哪里不容易理解, 或者你说下你不理解的地方?

from slim.

谢谢关于分支信息的解答。
关于不允许索引过小文件的问题。我们使用slimtrie，就是根据key和slimtrie最终找到磁盘上的offset并在这个 位置读取文件信息。如果索引很小的文件，那么一定可以确保offset之后一次性读取到文件。这样不是期望的吗？
如果文件过小，会造成什么困扰呢?

from slim.

关于不允许索引过小文件的问题。我们使用slimtrie，就是根据key和slimtrie最终找到磁盘上的offset并在这个 位置读取文件信息。如果索引很小的文件，那么一定可以确保offset之后一次性读取到文件。这样不是期望的吗？
如果文件过小，会造成什么困扰呢?

会导致非常多的索引的条目.内存可能不够用

from slim.