zset 是 redis 中一种有序、不重复的数据类型，每个元素都有一个分值，它可用于实现排行榜单，其底层采用压缩表 ziplist 或跳表 skiplist 的数据结构实现
Zset 的两种数据结构
压缩表 ziplist
当 redis 插入第一个元素时，同时满足以下条件，就会以 ziplist 创建跳表
- 节点数量<128 （可通过 server.zset_max_ziplist_entries 设置）
- 节点的长度<64（可通过 server.zset_max_ziplist_value 设置）
当选择用 ziplist 实现 zset 后，以后插入的节点若不满足以上任一个条件，就会转为 skiplist
跳表 skiplist
跳表的本质是一个多层链表，它能快速地查询、插入、删除【时间复杂度均为 O(logn)】，所以它的查询速度媲美平衡二叉树，而且它的数据结构比平衡二叉树简单，结构示意图如下:
特点：
- 跳表的最底层拥有所有的元素
- 跳表每一层都是一个链表，除了最底层是原始链表，层次逐渐往上可分别划分为一级索引层、二级索引层…
- 跳表插入元素时，会先随机生成出一个“层次数字”，然后元素会插入到这个层次的所有底层，直到原始链表层
- 如果一个元素存在与某个索引层，那么这个元素也会存在于低于它的所有索引下层，如元素在第 99 索引层，那么由上到下从 99 索引层直到原始链表层都会存在该元素
- 空间换时间，跳表查找变快了，但是要存储许多索引层，故空间开销变大了
/**
* 产生节点的高度。使用抛硬币
*
* @return
*/
private int getRandomLevel() {
// 可知，元素的插入层次i从1开始自增，随机到哪一层的概率就像抛硬币一样，都是50%，故i越往后，其概率越小(每次都*0.5)
// 第一层概率：0.5，第二层0.5*0.5=0.25，...
int lev = 1;
while (random.nextInt() % 2 == 0) {
lev++;
}
// MAX_LEVEL为跳表的最大层级
return lev > MAX_LEVEL ? MAX_LEVEL : lev;
}- 插入节点
- 插入的时间复杂度为 O(logn)，每次插入都会先查找到要插入的位置（查找的时间复杂度就已经是【O(logn)】了，找到后直接插入【O(1)】，所以总的为【O(logn)】），删除也是同理为 O(logn)
- 每个节点的插入层次是通过 getRandomLevel()随机出来的，插入层次互不影响
以下模拟节点插入：
- 查找
查找节点时，从高索引层往低索引层查找：
一开始元素在高层从链表由前往后查找，直到要查找的目标元素在该层的某两个相邻元素之间，就会往下跳到下层的同一个位置，继续从同一位置向链表尾方向遍历查询->重复上面的过程，直到查找到目标元素
查找时每一层都跳过部分元素，进而加快了查找效率，以下模拟节点查找：
跳表简单实现
import java.util.Random;
public class SkipList {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node();
private Random random = new Random();
public Node find(int value){
Node p = head;
for(int i = levelCount - 1; i >= 0; i--){
//如果在这一个level上存在下一个数据节点且下一个数据节点的值小于value，p往后挪一个
//直到这一个level走完或者值在区间内，切换下一个层级
while(p.forwards[i] != null && p.forwards[i].data < value){
p = p.forwards[i];
}
}
//到最下层依照上面的索引找到的位置往后找一位即可判断
if(p.forwards[0] != null && p.forwards[0].data == value) return p.forwards[0];
return null;
}
public void insert(int value){
Node p = head;
int level = randomLevel();
Node node = new Node();
node.data = value;
node.maxLevel = level;
//记录要更新的node
Node update[] = new Node[level];
//插入一个新的node，主要目标更新保存的forwards
for(int i = level; i >= 0; i--){
//在计算得到的level中依次找适合的位置
while(p.forwards[i] != null && p.forwards[i].data < value){
p = p.forwards[i];
}
update[i] = p;
}
//更新指向
for(int i = 0; i < level; i++){
node.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = node;
}
if(levelCount < level) levelCount = level;
}
public void delete(int value){
Node[] deleteNode = new Node[MAX_LEVEL];
Node p = head;
for(int i = levelCount - 1; i >=0; i--){
//确定每个层级中要删除的value对应的node
while(p.forwards[i] != null && p.forwards[i].data < value){
p = p.forwards[i];
}
//当前level中要删除的p，更新到node数组中
deleteNode[i] = p;
}
//从底层扫，每层删除
if(p.forwards[0] != null && p.forwards[0].data == value){
//根据上面deleteNode[]中保存的要删除的node，更新前后的指向
for(int i = levelCount - 1; i >= 0; i--){
if(deleteNode[i] != null && deleteNode[i].forwards[i].data == value){
deleteNode[i].forwards[i] = deleteNode[i].forwards[i].forwards[i];
}
}
}
}
public void printAll(){
Node p = head;
while(p.forwards[0] != null){
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
private int randomLevel() {
int level = 0;
for(int i = 0; i < MAX_LEVEL; i++){
if(random.nextInt()%2 == 1){
level++;
}
}
return level;
}
class Node{
private int data;
//核心在这个forwards数组，他存放了各个level索引的下一个数据节点
private Node[] forwards = new Node[MAX_LEVEL];
private int maxLevel;
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("{data: ");
sb.append(data);
sb.append("; level: ");
sb.append(maxLevel);
sb.append(" }");
return sb.toString();
}
}
}