1

我很快就要考试了，我想知道如何解决这些关于索引的问题：

1.数据库由关系 R(A,B,C) 组成。A 和 B 是整数 [0,10 000]（每个 4B），C 是 varchar(20) (20B)。关系 R 由 10^6 个元组组成。块大小为 2048 B。

A）如果我们询问这个查询，如果我们在 B 上有一个 B+-tree 索引，我们必须读取多少块（最好和最差）：

从 R 中选择 C，其中 A=100 且 B=10

B) 索引 A 有意义吗？如果是，哪种类型的指标最好？

另一个类似的问题是：

2.数据库由关系R（A，B，C）组成。A 和 B 是整数 [0,10 000]，C 是 varchar(150)。关系 R 由 10^6 个元组组成。块大小为 2048 B，A、B 是键。

A）如果我们询问查询“ SELECT C FROM R WHERE A=4711 并且：

  • 我们没有索引。
  • 我们在 A 和 B 上有一个 B+-tree 索引。

b) 单独索引 B 和单独索引 A 是否有意义，而不是在 A 和 B 上设置一个索引。什么类型的索引是最好的？

编辑：

这是我所做的：

问题 1 A)

元组的大小 = 20+4+4=28 B

2048/28=73 元组/块向下舍入

10^6/73= 13 699 个块代表整个关系，向上取整

索引读数：4*n+4(n+1)<=2048 B => n=255 向下舍入

B+树的第一层= 255<10^6 否

B+树的第二层= 255*256<10^6 否

B+树的第三层= 255*256*257>10^6 是的，10^6 个元组可以放入高度为 3 的 B+树。

数据读取：如果我们假设 A=100 的概率为 1/10001，B=10 的概率相同，那么我们有：

1/10001*1/10001*10^6 向上取整 = 1 个元组

在最坏和最好的情况下：1 个元组 = 1 个块

然后我们有 3+1 块读数

这样对吗？

我不知道怎么做B）..

我真的不知道如何回答问题2 ..请帮帮我

4

1 回答 1

0

只是一些笔记。您的 1A 最佳情况似乎几乎是正确的（有点，但 se 补充说：在底部），但我认为您的块大小计算是错误的。只有（的值）B 和指向所需磁盘块的指针/引用应该存储在 b+ 索引树中。A 和 C 都不应该在 b+ 树中。

而你最坏的情况是真的错了。没有要求 B 是唯一的，在谈论最坏情况时也不需要做概率。

所以想象一下如果所有元组中的 B=10 会发生什么。然后你必须阅读它们以找到 A=100 的值。（请记住，您被要求提供最佳/最坏情况而不是平均情况）。

这个最坏的例子也是你解决问题 1B 的提示。如果您有太多具有相等 B 值的值，以至于它们无法位于几个块中，则索引可能很有用。（你可以做精确的数学）。

2A好像没那么难。如果我们没有索引，那么您需要在最好的情况下读取 1 个块，在最坏的情况下读取所有块。（这假设 A 是唯一的。这就是 A 作为键的含义对吗？）

但我对最后一个问题有点困惑。如果 A 和 B 是 2 个不同的（外来的？？？）键，那么在它们上都有一个组合索引似乎是错误的。

ps：这是几年前我在大学做的，所以我可能错了，但我希望我至少给了你一些思考：}

添加： - - - - - - - - -

我关于您计算单个节点中可以拥有多少条目的注释似乎真的不正确。试试这个：（仍然来自记忆，对任何错误深表歉意）。

b+ 树中的一个条目，包含 B 的 2 个值（最小值/最大值）和一个包含最小值和最大值之间值的块的磁盘块引用。所以每个条目是 12 个字节（假设 4 字节块引用），因此您可以在每个块中存储 2048/12=170 个条目。

于 2011-03-12T18:06:52.243 回答