Redis—跳躍表

一、跳躍表簡介

跳躍表(skiplist)是一種隨機化的數據結構,由 William Pugh 在論文《Skip lists: a probabilistic alternative to balanced trees》中提出,是一種可以與平衡樹媲美的層次化鏈表結構——查找、刪除、添加等操作都可以在對數期望時間下完成,以下是一個典型的跳躍表例子:

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/p2L6chUyNqBxsXDVf82lPw