0

我在扩展应用程序时遇到了一些困难，因此决定在这里提出一个问题。

考虑一个关系数据库（比如 mysql）。假设它允许用户发布帖子，并且这些帖子存储在post表中（具有字段：）postid, posterid, data, timestamp。因此，当您按新近度排序检索所有帖子时，您只需使用posterid = you和获取所有帖子order by date。很简单。

此过程将使用时间戳作为索引，因为它具有最高的基数并且正确。因此，除了查看索引之外，还需要从磁盘中提取 1 行来完成此任务。惊人的！

但是，假设自您上次发布以来，其他用户（在系统中）又发布了 100 万条帖子。然后，为了获取您的最新帖子，数据库将再次将索引与时间戳挂钩，并且我们不知道从那时起发生了多少帖子（或者我们至少应该手动估计并设置首选键）？然后我们浪费了查看一百万零一行只是为了获取一行。

此外，来自多个任意用户的一组帖子将是用例之一，因此我无法创建像 userid_timestamp 这样的字段来创建子索引。

我看错了吗？或者必须从根本上改变应用程序以允许这样的操作至少在某种程度上有效地发生？

4

3 回答 3

3

索引

如果你有一个查询：... WHERE posterid = you ORDER BY timestamp [DESC]，那么你需要一个关于{posterid, timestamp}的复合索引。

  • 通过索引前沿（posterid）上的范围扫描来查找给定用户的所有帖子。
  • 查找用户最旧/最新的帖子可以在单个索引查找中完成，这与 B-Tree 高度成正比，与 log(N) 成正比，其中 N 是索引行数。

要了解原因，请查看Anatomy of an SQL Index。

聚类

“正常”B-Tree 索引的叶子持有指向索引行的“指针”（物理地址），而行本身驻留在称为“表堆”的单独数据结构中。可以通过将行直接存储在 B-Tree 的叶子中来消除堆，这称为聚类。这有其优点和缺点，但如果您有一种主要的查询类型，那么通过集群消除表堆访问绝对是值得考虑的事情。

在这种特殊情况下，可以像这样创建表：

CREATE TABLE T (
    posterid int,
    `timestamp` DATETIME,
    data VARCHAR(50),
    PRIMARY KEY (posterid, `timestamp`)
);

MySQL/InnoDB对它的所有表进行集群，并使用主键作为集群键。我们没有使用代理键 ( postid)，因为聚簇表中的二级索引可能很昂贵，而且我们已经有了自然键。如果您确实需要代理键，请考虑将其设为备用键并保持通过自然键建立的集群。

于 2012-12-25T16:46:26.227 回答
1

对于像这样的查询

where posterid = 5
order by timestamp

或者

where posterid in (4, 578, 222299, ...etc...)
order by timestamp

建立一个索引，(posterid, timestamp)数据库应该自己选择它。

编辑 - 我刚刚用 mysql 试过这个

CREATE TABLE `posts` (
    `id` INT(11) NOT NULL,
    `ts` INT NOT NULL,
    `data` VARCHAR(100) NULL DEFAULT NULL,
    INDEX `id_ts` (`id`, `ts`),
    INDEX `id` (`id`),
    INDEX `ts` (`ts`),
    INDEX `ts_id` (`ts`, `id`)
)
ENGINE=InnoDB

我用大量数据填充它，并且

explain
select * from posts where id = 5 order by ts

选择id_ts索引

于 2012-12-25T16:35:55.153 回答
0

假设您使用哈希表来实现您的数据库 - 是的。哈希表没有排序，除了迭代所有元素以找到最大值之外别无他法。

但是，如果您使用一些有序的 DS，例如B+ 树（实际上对磁盘和数据库进行了优化），情况就不同了。

您可以将元素存储在按用户（主要顺序/比较器）和日期（次要比较器，降序）排序的 B+ 树中。一旦有了这个 DS，就可以在O(log(n))磁盘寻道中找到第一个元素，方法是找到与主要条件（用户 ID）匹配的第一个元素。

我不熟悉数据库的实现，但是 AFAIK，其中一些确实允许您基于 B+ 树创建索引- 通过这样做，您可以更有效地找到用户的最后一篇文章。

附言

确切地说，“最大”元素或排序的概念在关系代数中没有得到很好的定义。没有最大运算符。要获得R具有单列的表的最大元素，a实际上应该创建该表的笛卡尔积并找到该条目。严格关系代数中没有 max 和 sort 运算符（尽管它确实存在于 SQL 中）

(Assuming set, and not multiset semantics):
MAX = R \ Project(Select(R x R, R1.a < R2.a),R1.a)
于 2012-12-25T15:31:13.120 回答