database - 索引数据输入的替代方案 1

Question

在索引中存储数据条目的三种选择之一是数据条目k*，它是具有搜索键值k的实际记录。我的问题是，如果您要将实际记录存储在索引中，那么创建索引的意义何在？

Answer 1

This is an extreme case, because it does not really correspond to having data entries separated by data records (the hashed file is an example of this case).

(M. Lenzerini、R. Rosati， Database Management Systems: Access file manager and query evaluation ，罗马“La Sapienza”大学，2016 年)

替代方案 1 通常用于直接索引，例如在 B 树和哈希索引中(另请参阅 Oracle， Building Domain Indexes )

---

让我们举一个具体的例子。

我们有一个关系R(a,b,c)并且我们有一个使用替代方案2的聚集 B⁺⁠-⁠树在搜索键a上。由于树是聚类的，关系R必须按a排序。

现在，我们假设关系的常见查询是:

SELECT *
FROM R
WHERE b > 25

所以我们想建立另一个索引来高效支持这种查询。

情况 1:带有 alt 的聚类树。 2

我们知道，具有替代方案 2 的聚类 B⁺⁠-⁠树对于范围查询来说是高效的，因为它们只需要搜索第一个好的结果(比如一个带有 b=25)，然后对该结果指向的关系页面进行 1 页访问，最后扫描该页面(最终扫描其他一些页面)，直到记录落入给定范围内.

总结一下:

• 搜索树中的第一个好结果。 成本:log_f(ℓ)
• 使用找到的指针转到特定页面。 成本:1
• 扫描该页面以及最终的其他页面。 成本:数字。相关页面数

最终成本(以页面访问次数表示)为

log_f(ℓ) + 1 + #relevant-pages

其中 f 是扇出，ℓ 是叶数。

不幸的是，在我们的例子中，搜索键 b 上的树必须是非聚集的，因为关系已经按 a 排序

情况 2:具有 alt 的非聚类树。 2(或3)

我们还知道，B⁺⁠-⁠树在非集群时在范围查询中效率不高。事实上，有一棵具有替代方案 2 或 3 的树，在树中我们只存储指向记录的指针，因此对于落在范围内的每个结果，我们必须对潜在的不同页面进行页面访问(因为该关系相对于索引具有不同的顺序)。

总结一下:

• 搜索树中的第一个好结果。 成本:log_f(ℓ)
• 跟随扫描叶子(可能还有其他叶子)并对落在该范围内的每个元组进行不同的页面访问。 成本:数字。其他相关叶子的数量 + 数量。相关元组

最终成本(以页面访问次数表示)为

log_f(ℓ) + #other-relevant-leaves + #relevant-tuples

请注意，元组的数量相对于页数来说更大!

情况 3:具有 alt 的非聚类树。 1

使用替代方案 1，我们拥有树中的所有数据，因此为了执行查询，我们:

• 搜索树中的第一个好结果。 成本:log_f(ℓ)
• 跟随扫描叶子(也可能是其他叶子)。 成本:数字。其他相关叶子

最终成本(以页面访问次数表示)为

log_f(ℓ) + #other-relevant-leaves

这甚至小于(或至多等于)情况 1 的成本，但这是允许的。

---

我希望我说得足够清楚。

注意成本以页面访问次数表示，因为从/到第二个存储的 I/O 操作在时间上是最昂贵的(我们忽略扫描主内存中整个页面的成本，但我们只考虑访问它的成本)。