0

假设您正在编写一个博客网站。它显示按“优先级”排序的多个作者最近的博客文章。最高优先级。优先级由以下公式确定:

  1. 这篇文章最近是如何发布的
  2. 吸引了多少评论

订单必须始终实时准确。

按优先级排序很容易。问题是,假设我们的网站非常受欢迎,评论以每分钟数百条的速度飞来。他们飞进了几十个帖子。

有处理这种情况的模式吗?换句话说,我们能不能做得更好,而不仅仅是在帖子上有评论时更新优先级字段,然后在每次加载页面时对帖子进行排序?缓存发布订单并没有多大帮助,因为大量的用户活动会导致订单频繁更改。

对于“模式”,我是从代码和数据库模式的角度讲的。

4

1 回答 1

0

您可以使用平衡二叉树(例如红黑树)来存储排序后的索引,这应该比每次都对整个索引进行排序时更新速度更快。

使用 Java-ish 伪代码,这看起来像

Tree tree;

Node {
    int priority;

    incrementPriority() {
        priority = priority + 1;
        if(priority > tree.nextHighestNode(this)) {
            tree.remove(this);
            tree.add(this);
        }
    }

    decrementPriority() {
        priority = priority - 1;
        if(priority < tree.nextLowestNode(this)) {
            tree.remove(this);
            tree.add(this);
        }
    }
}

如果更改节点的优先级意味着它位于无效的树位置(意味着它高于应该是下一个最高节点,或者低于应该是下一个最低节点),那么它会被移除并重新 -添加到树(负责重新平衡自身)。插入是 O(log(n)),但通常(当没有插入/删除时)更新优先级是一个恒定时间操作。

红黑树是平衡二叉树的通常实现方式,但也有替代方案,例如Tango 树可能更适合这里,因为它是在线实现。最大的问题是并发性 - 理想情况下,您希望能够使用某种 AtomicInteger 实现节点的优先级字段(允许原子增量和减量;相当多的语言都有这样的东西),这样你就不会了每次更改时都需要锁定字段,但是很难将优先级与相邻节点的优先级进行原子比较。

作为替代方案,您可以将所有内容存储在数组或链表中,并在它们的优先级发生变化时交换相邻元素 - 这样您就不需要每次都进行完整排序,这与平衡二叉树不同,其中删除和插入元素是 O(log(n)),交换两个相邻的数组/列表元素是常数时间。唯一的问题是使用数组添加一个全新的元素会很昂贵,因为您需要移动数组的所有元素;它也将是 O(n) 与列表,因为您需要遍历列表直到找到插入项目的正确位置,但这可能比数组更可取,因为您不需要移动任何相邻的元素(这将减少您需要执行的锁定量)。

于 2013-04-25T02:25:20.823 回答