1

这是来自家庭作业：

假设每页（磁盘块）有 16K 字节，每个 KVP 有 8 字节。因此我们决定使用最小尺寸 (16000/8)/2 = 1000 的 B-tree。让 T 成为这样的 B-tree 并假设 T 的高度为 3。可以是的最小和最大键数是多少存储在 T? 简要证明你的答案。

由于 B 树的特性，请注意以下几点：
每个节点最多有 2000 个键
每个节点至少有 1000 个键（根节点除外）

我无法理解内存如何限制键的数量。在我看来，由于每个页面有 16000 字节的空间并且每个键占用 8 个字节，那么每个页面可以存储 2000 个键，这是每个级别可以存储的最大键数。

以下是我的计算：
最小键数 = 1000(1001)(2) + 1 = 至少 2002001 个键
（因为根不限于至少 1000 个键）
最大键数 = 2000(2001)(2001 ) = 最多 8008002000 个键

我觉得我错过了一些重要的事情，因为问题不可能这么简单。

4

1 回答 1

2

有点明显的提示：每个非叶节点都有一个右孩子和一个左孩子。另外，还有指向键/值对的指针，但是它们可能会被存储。（1000 似乎很多......）想想你将如何存储这 1000 多个数据点。

+---------------+
| 根 |
| 左 右 |
+----+------+----+
    | |
    | +----+----------+
    | | 2级+---数据：列表、哈希表等
    | | 左 右 |
    | +----+------+----+
    | | |
    | 等等等等
    |
+----+----------+
| 2级+---数据：列表、哈希表等
| 左 右 |
+----+------+----+
    | |
    等等等等
于 2010-11-07T03:48:28.347 回答