跳跃表的应用

在Redis中，跳跃表主要应用于有序集合的底层实现（有序集合的另一种实现方式为压缩列表）。

Redis的配置文件中关于有序集合底层实现的两个配置。

1）zset-max-ziplist-entries 128:zset采用压缩列表时，元素个数最大值。默认值为128。

2）zset-max-ziplist-value 64:zset采用压缩列表时，每个元素的字符串长度最大值。默认值为64。

zset添加元素的主要逻辑位于t_zset.c的zaddGenericCommand函数中。zset插入第一个元素时，会判断下面两种条件：

❏ zset-max-ziplist-entries的值是否等于0；

❏ zset-max-ziplist-value小于要插入元素的字符串长度。

满足任一条件Redis就会采用跳跃表作为底层实现，否则采用压缩列表作为底层实现方式。

一般情况下，不会将zset-max-ziplist-entries配置成0，元素的字符串长度也不会太长，所以在创建有序集合时，默认使用压缩列表的底层实现。zset新插入元素时，会判断以下两种条件：

❏ zset中元素个数大于zset_max_ziplist_entries；

❏ 插入元素的字符串长度大于zset_max_ziplist_value。

当满足任一条件时，Redis便会将zset的底层实现由压缩列表转为跳跃表。

跳跃表的原理简单，其查询、插入、删除的平均复杂度都为O(logN)。跳跃表主要应用于有序集合的底层实现。