数据库索引：示例

Question

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

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

A) 如果我们询问此查询，如果 B 上有 B+ 树索引，我们必须读取多少个块（最佳和最差）：

SELECT C FROM R WHERE A=100 and 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+ 树索引， 那么在最好和最坏的情况下我们必须读取多少个块b )

分别为 B 和 A 建立索引而不是在 A 和 B 上建立一个索引是否有意义。

编辑：

这是我所做的：

>问题1 A)

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

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

10^6/73= 13 699 个块，用于整个关系，向上舍入

< em>索引读数： 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..请帮助我

Answer 1

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

而你最坏的情况确实是错误的。不要求B唯一，谈论最坏情况也不需要做概率。

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

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

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

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

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

补充： -------------- ---

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

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