跳躍表(跳表)

簡介

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

實例

對比有序鏈表和跳躍表，從鏈表中查詢出51

• 有序鏈表

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

• 跳躍表

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

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

在第1層，41節點比51節點小，繼續向后，61節點比51節點大，所以從41向下

在第0層，51節點為要查找的節點，節點被找到，共查找4次。

從此可以看出跳躍表比有序鏈表效率要高

總結

以上是生活随笔為你收集整理的[Redis6]跳跃表(跳表)的全部內容，希望文章能夠幫你解決所遇到的問題。

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