經常更新的排序數據的模式

假設您正在撰寫博客網站。它顯示由多位作者按「優先級」排序的最近博客文章。頂級的最高優先級。重點是通過一些公式涉及確定：經常更新的排序數據的模式

怎麼最近的帖子發表
有多少評論吸引

訂單必須始終實時準確。

按優先級排序很容易。問題是讓我們說，我們的網站非常受歡迎，評論以每分鐘數百的速度飛行。他們飛過幾十個帖子。

有沒有處理這種情況的模式？換句話說，我們可以做什麼，而不僅僅是在對帖子發表評論時更新優先級字段，然後在每次加載頁面時對帖子進行排序？緩存郵政訂單沒有多大幫助，因爲繁重的用戶活動導致訂單頻繁更改。

對於「模式」，我從代碼和數據庫模式的角度來講。

來源

2013-04-24 S. Valmont

您可以使用平衡二叉樹（例如紅黑樹）來存儲排序後的索引，與每次對整個索引進行排序相比，這會使其更快地更新。

使用Java上下的僞代碼，這將看起來像

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）），但通常（當沒有插入/移除時）更新優先級是一個恆定的時間操作。

Red-black trees是多麼平衡的二叉樹通常是如何實現的，但也有其他選擇，例如Tango tree可能更合適，因爲它是一個在線實現。最大的問題在於併發性 - 理想情況下，您希望能夠使用某種AtomicInteger實現節點的優先級字段（允許原子增量和遞減;不少語言都有類似的情況）每次更改它時都需要鎖定字段，但很難自動比較優先級和相鄰節點的優先級。

作爲替代方案，您可以將所有內容都存儲在數組或鏈表中，並在優先級更改時交換相鄰元素 - 這樣您就不需要每次都進行完全排序，而不像平衡二叉樹那樣刪除和插入元素是O（log（n）），交換兩個相鄰的數組/列表元素是恆定時間。唯一的問題是添加一個全新的元素將會花費數組，因爲您需要移動所有數組的元素;它也會是O（n）和一個列表，因爲你需要遍歷列表，直到找到正確的位置來插入項目，但是這可能比數組更好，因爲你不需要移動任何相鄰的元素（這會減少你需要做的鎖定量）。

來源

2013-04-25 02:25:20

經常更新的排序數據的模式

回答

相關問題