0

是否有支持在连续值范围内进行高效查询/索引的数据库技术？例如考虑以下数据集

Name      Age
Alice     25
Bob       35
Charlie   26
Diane     39
Edward    19
...       ...

现在想象一下，我想查询所有 20 多岁的人的姓名。我可以在许多数据库系统中表达这个查询。有没有支持这种高效/次线性查询的系统？亚线性是指它不需要查看表/数据库中的每个条目，但可以通过查看其他一些数据结构来快速选择相关行。我正在寻找诸如索引之类的东西，但是过度有序和连续的数据。我要过滤的特定有序/连续列的类型为 Datetime。

请注意，我不是在寻找解决此问题的查询。我正在寻找一个示例数据库系统，它支持对有序连续数据进行高效（次线性）过滤。

如果不存在这样的系统，我也很乐意了解该领域的研究/论文。

4

3 回答 3

2

如果这类似于一个非常大的数据仓库事实表，上面有一个必须有效查询数据的时间组件（例如，DATE_OF_SALE），那么一个常见的实现将是一个根据该值分区的关系数据库表。

在 Oracle 中，这通常是范围分区，所以我将说明它是如何在内部实现的。

可以将常规未分区表视为一组列和表元数据（表名、列名和数据类型等）和存储实际数据的“物理”数据段。全表扫描要求为高水位线下的每个块读取此数据段。

分区将表分成多个段，每个段在逻辑上都被限制为保存一组特定的数据。这可能是由特定列（分区键）的值列表、应用于列的哈希函数的结果定义的集合，或者在这种情况下是列的值范围。

查询优化器检测分区键列上是否存在谓词，并尝试隔离可能包含候选数据的最小分区集。然后可以通过专用于每个分区的索引来扫描或访问这些。这被称为分区修剪，由于从考虑中消除了大型数据集，因此可以更快地扫描数据。

在更多设计的系统中，例如 Oracle 的 Exadata，可能存在存储连续数据块集的列的最大值和最小值的结构，大小在低兆字节范围内。在这种情况下，对表或分区的完整扫描可以通过消除其中存在候选行的可能性来消除对这些数据块集的扫描。Oracle 将这些结构称为存储索引。

因此，为 Oracle 重度方法道歉，但类似的实现存在于其他关系和非关系数据库中，它们可以提供比索引更高的性能。

顺便说一句，索引的一个问题是表数据没有隐式组织，因此对表数据的 20% 的索引扫描很可能由于重复扫描数据的效率低于对数据的完整扫描表的数据段的单块访问。一些 RDBMS 允许设置行的物理顺序——PostgreSQL 允许通过索引的列对表进行集群，这使得按照索引的顺序一次性重写表，从而改进了基于索引的访问，直到由于添加新行或更新现有行，数据变得杂乱无章。

于 2013-09-18T19:29:59.563 回答
2

如果您的意思是“高效”和“次线性”，如“不是全表扫描”，那么如果您在列上放置索引，任何主要的关系数据库都可以做到这一点。

整数列和时间戳列都非常适用于此，因为它们的排序非常简单，并且列的宽度是固定的并且很小 - 因此索引非常有效。

由于索引通常是 btree 索引（或其变体），因此索引是默认排序的。范围查询只是意味着：选择适当的子树并完成。使用此标准遍历树是次线性的。

示例：使用 PostgreSQL：

> select count(*) from objects;
34215157
Time: 4423,262 ms

> explain select * from objects where objects_pkey between 42 and 42000;
                                 QUERY PLAN                                      
-------------------------------------------------------------------------------------
 Index Scan using objects_pkey on objects  (cost=0.00..1920.84 rows=40292 width=288)
   Index Cond: ((objects_pkey >= 42) AND (objects_pkey <= 42000))

> select count(*) from objects where objects_pkey between 42 and 42000;
 count 
-------
 41959
Time: 15,403 ms

这意味着：表很大，不适合内存。使用整数列的索引扫描受两个标准的约束（意思是：高效访问）。获取约 40k 行仅需 15 毫秒。

顺便说一句：您要求的这种访问 a) 没有什么新鲜的或令人兴奋的，b) 正是这种查询关系数据库的诞生和调整了大约三年。

于 2013-09-18T19:15:09.270 回答
-1

MySQL 是一个数据库系统，您可以在其中执行高效的查询。例如，要获取所有 20 多岁的人，您可以使用以下查询：
SELECT Name FROM my_table WHERE Age BETWEEN 20 AND 29;

于 2013-09-18T18:56:12.327 回答