為什么80%的碼農都做不了架構師？>>> ??

上文為什么超長列表數據的翻頁技術實現復雜提到了超長列表翻頁技術設計上一些問題，今天討論下部分解決思路。

前新浪同事 @pi1ot 最近在程序員雜志發表的一篇文章《門戶級UGC系統的技術進化路線》也是超長列表的一個經典案例，在正式展開思路之前，我們也不妨了解一下此文所說新浪評論系統的演進思路。

從文中看到幾個版本的列表翻頁實現方案

3.0版

3.0系統的緩存模塊設計的比較巧妙，以顯示頁面為單位緩存數據，因為評論頁面是依照提交時間降序排列，每新增一條新評論，所有帖子都需要向下移動一位，所以緩存格式設計為每兩頁數據一個文件，前后相鄰的兩個文件有一頁的數據重復，最新的緩存文件通常情況下不滿兩頁數據。

此方案由于每頁的條數是定長的，因此主要采用緩存所有列表的方案。但為了數據更新的便利，緩存結構比較復雜。從今天多年之后的眼光來看，這種設計不利于理解、擴展及維護。因此目前大多不傾向使用這種方案。

4.0版

解決方案是在MySQL數據庫和頁面緩存模塊之間，新建一個帶索引的數據文件層，每條新聞的所有評論都單獨保存在一個索引文件和一個數據文件中，期望通過把對數據庫單一表文件的讀寫操作，分解為文件系統上互不干涉可并發執行的讀寫操作，來提高系統并發處理能力。在新的索引數據模塊中，查詢評論總數、追加評論、更新評論狀態都是針對性優化過的高效率操作。從這時候起，MySQL數據庫就降到了只提供歸檔備份和內部管理查詢的角色，不再直接承載任何用戶更新和查詢請求了。

使用自定義索引的方式，由于未與相關人員交流細節，推斷應該是類似數組的結構。

從上述案例看到，評論系統是一種典型的超長列表數據結構，如果再MySQL的基礎上來做，需要設計額外的索引結構來實現高效的翻頁功能。

由于超長列表的翻頁實現成本高主要是由于列表索引的B-TREE結構方面原因，B-TREE結構能快速查找到某個key，但不是為葉子節點的Range訪問而設計，因此主要解決思路也是圍繞B-TREE的range訪問而進行優化。

首先、從原理來看，可以在B-TREE增加以下2個二級索引字段：

• Count index?記錄每個非葉子節點下的條目數，這樣可以幫助快速定位到任意的offset；
• Offset index?記錄部分葉子節點的offset，比如每隔1000個id記錄一個offset如下，并保存在另外一個列表中，當需要查找某個offset的時候，則可以利用附近已經記錄offset的id來定位目的地位置。比如當翻頁到1010時，如果offset index記錄了[1000: id10345]，則可以從id10345往后10個元素找到10010。

[ {"1000":10345}, {"2000":13456}, {"3000":22345}, {"4000":56789}, {"5000":66788} ]

這2個字段可以同時使用，也可以只用其中一個。如圖

再看如何將上述方法應用到具體的實現中。由于本文主要討論MySQL環境，MySQL要在B-TREE上額外保存一些信息需要修改MySQL源代碼，修改門檻較高，因此更簡單方法是將上述二級索引通過應用層保存在另外的表中。

一種非嚴格意義的count index實現如下：

CREATE TABLE IF NOT EXISTS `second_index` (`id` int(11) NOT NULL AUTO_INCREMENT,`uid` int(11) NOT NULL,`yymm` int(11) NOT NULL,`index_count` int(11) NOT NULL,PRIMARY KEY (`id`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8;INSERT INTO `second_index` (`id`, `uid`, `yymm`, `index_count`) VALUES (1, 1, 1409, 123), (2, 1, 1410, 2342), (3, 1, 1411, 534), (4, 1, 1412, 784), (5, 1, 1501, 845);

一種offset index實現如下：
在第一次用戶翻頁到某個offset位置時，在redis直接保存offset, id。當有其他請求來查找offset之后數據時，可以從offset的位置往后掃描。如果列表的數據發生了變化，需要及時將Redis保存的offset index刪除。

以上2種方法已經在生產環境使用。

@icycrystal4 對此文所提方法亦有貢獻。

轉載于:https://my.oschina.net/boltwu/blog/424231

總結

以上是生活随笔為你收集整理的为什么超长列表数据的翻页技术实现复杂（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。