此 B 树中键的最大和最小数量
这是来自家庭作业：
假设每个页（磁盘块）有16K字节，每个KVP有8字节。因此 我们决定使用 minsize (16000/8)/2 = 1000 的 B 树。令 T 为这样的 B 树， 假设 T 的高度为 3，那么最小和最大键数是多少 可以存储在T中吗？简要证明你的答案。
根据 B 树的属性，请注意以下几点：
每个节点最多有2000个key
每个节点至少有1000个键（根节点除外）
我无法理解内存如何限制键的数量。 在我看来，由于每个页面有 16000 字节的空间，每个密钥占用 8 字节，那么每个页面可以存储 2000 个密钥，这是无论如何可以在每个级别存储的最大密钥数量。
以下是我的计算：
最小密钥数量 = 1000(1001)(2) + 1 = 至少 2002001 个密钥
（因为根不限于拥有至少 1000 个密钥）
最大键数 = 2000(2001)(2001) = 8008002000 最大键数
我觉得我错过了一些重要的东西，因为问题不可能这么简单。
This is from a homework assignment:
Assume that each page (disk block) has 16K bytes and each KVP has 8 bytes. Thus
we decide to use a B-tree of minsize (16000/8)/2 = 1000. Let T be such a B-tree and
suppose that height of T is 3. What is the minimum and maximum number of keys
that can be stored in T? Briefy justify your answer.Note the following due to the properties of B-trees:
Each node has at most 2000 keys
Each node has at least 1000 keys (except for the root node)
I am having trouble understanding how the memory is limiting the number of keys.
It seems to me that since each page has 16000 bytes of space and each key takes up 8 bytes, then each page can store 2000 keys which is the max number of keys that can be stored at each level anyways.
The following are my calculations:
Minimum number of keys = 1000(1001)(2) + 1 = 2002001 keys at minimum
(Since the root is not constrained to having at least 1000 keys)
Maximum number of keys = 2000(2001)(2001) = 8008002000 keys at maximum
I feel I am missing something vital as the question cannot be this simple.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
有点明显的提示：每个非叶节点都有一个右子节点和一个左子节点。另外，还有指向键/值对的指针，无论它们如何存储。 （1000 个似乎很多...）考虑一下您将如何存储这 1000 多个数据点。
+--------------+ | Root | | Left Right | +---+------+---+ | | | +---+----------+ | | Level 2 +---Data: List, hash table, whatever | | Left Right | | +---+------+---+ | | | | Etc Etc | +---+----------+ | Level 2 +---Data: List, hash table, whatever | Left Right | +---+------+---+ | | Etc EtcSomewhat blatant hint: Each non-leaf node has a right and a left child. Plus, there are pointers to key/value pairs, however they might be stored. (1000 seems like a lot...) Think about how you're going to store those 1000+ data points.
+--------------+ | Root | | Left Right | +---+------+---+ | | | +---+----------+ | | Level 2 +---Data: List, hash table, whatever | | Left Right | | +---+------+---+ | | | | Etc Etc | +---+----------+ | Level 2 +---Data: List, hash table, whatever | Left Right | +---+------+---+ | | Etc Etc