点赞再看，养成习惯，微信搜索「小大白日志」关注这个搬砖人。
文章不定期同步公众号，还有各种一线大厂面试原题、我的学习系列笔记。
广州这边封闭式管理好久了，今天终于周末可以出去溜溜了
什么是zset
zset是redis中一种有序、不重复的数据类型，每个元素都有一个分值，它可用于实现排行榜单，其底层采用压缩表ziplist或跳表skiplist的数据结构实现
zset的两种数据结构
- 压缩表ziplist
当redis插入第一个元素时，同时满足以下条件，就会以ziplist创建跳表
- 节点数量<128 （可通过server.zset_max_ziplist_entries设置）
- 节点的长度<64（可通过server.zset-max-zip以上任一个，都会list-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;
}
跳表skiplist
-
插入节点
- 插入的时间复杂度为O(logn)，每次插入都会先查找到要插入的位置（查找的时间复杂度就已经是【O(logn)】了，找到后直接插入【O(1)】，所以总的为【O(logn)】），删除也是同理为O(logn)
- 每个节点的插入层次是通过getRandomLevel()随机出来的，插入层次互不影响
以下模拟节点插入：
-
查找
查找节点时，从高索引层往低索引层查找：
一开始元素在高层从链表由前往后查找，直到要查找的目标元素在该层的某两个相邻元素之间，就会往下跳到下层的同一个位置，继续从同一位置向链表尾方向遍历查询->重复上面的过程，直到查找到目标元素
查找时每一层都跳过部分元素，进而加快了查找效率，以下模拟节点查找：
OK，如果文章哪里有错误或不足，欢迎各位留言。
创作不易，各位的「三连」是二少创作的最大动力！我们下期见！