跳躍表介紹

1、簡介

有序集合在生活中比較常見，例如根據成績對學生排名，根據得分對玩家排名等。對于有序集合的底層實作，可以用數組、平衡樹、連結清單等。數組不便元素的插入、删除；平衡樹或紅黑樹雖然效率高但結構複雜；連結清單查詢需要周遊所有效率低。Redis采用的是跳躍表。跳躍表效率堪比紅黑樹，實作遠比紅黑樹簡單。

2、執行個體

對比有序連結清單和跳躍表，從連結清單中查詢出51

1. 有序連結清單：

 要查找值為51的元素，需要從第一個元素開始依次查找、比較才能找到。共需要6次比較。

     2.跳躍表

從第2層開始，1節點比51節點小，向後比較。

21節點比51節點小，繼續向後比較，後面就是NULL了，是以從21節點向下到第1層