前言

做游戲的一般都有游戲排行榜的需求，要查一下某個uid的積分排名第幾，這里我給大家推薦之前我們使用的一種排序算法，跳表skiplist。

跳表是一個隨機化的數據結構。它允許快速查詢一個有序連續元素的數據鏈表。跳躍列表的平均查找和插入時間復雜度都是O(log n)，優于普通隊列的O(n)。性能上和紅黑樹，AVL樹不相上下，但跳表的原理非常簡單，目前Redis和LevelDB中都有用到。

跳表是一種可以替代平衡樹的數據結構。跳表追求的是概率性平衡，而不是嚴格平衡。因此，跟平衡二叉樹相比，跳表的插入和刪除操作要簡單得多，執行也更快。

跳表和平衡二叉樹

為什么跳表可以高效的獲取rank呢？只能說跳表的數據結構設計巧妙。

跳表本身提供的功能類似于平衡二叉樹以及高級變種，可以對目標值進行快速查找，時間復雜度為O(lgN)。但是跳表的實現原理比實現一顆高效的平衡二叉樹（比如紅黑樹）要簡單太多，這是跳表非常大的一個優勢。

關鍵在于，跳表計算某個score的排名次序，與在跳表中找到這個score的時間復雜度是一樣的，仍舊是O(lgN)。反觀二叉樹系列，它們找到一個值也很快，但是要想知道這個值排名第幾，似乎只能按照先序遍歷的方式來統計排在前面的值個數。

其實跳表獲取排名的思路也是數一下前面有多少個值，但因為”跳躍”的關系，統計的過程被加速了，因而rank效率更高。

跳表find原理

因為rank的計算過