吃透redis数据结构（二）

目录

五、ZSet 有序集合 

1. ZSet 底层是什么结构？

插入元素时：

删除或者更新元素时：二者都要删除更新，保持数据一致。

为什么跳表的层高随机？

2. 为什么 ZSet 用跳表不用红黑树？

范围遍历：

跳表实现逻辑简单，没有复杂的旋转操作：

内存占用平均下来更低：

3. ZSet 的 member 和 score 是否可重复？

4. ZSet 业务场景？

六、GEO 地理位置 

1. GEO 底层是什么数据结构？

2. 为什么 GEO 没有删除命令 GEODEL？怎么删除？

3. GEO 的缺点是什么？

4. GEO 适用场景？

七、Bitmap & HyperLogLog 

1. Bitmap 底层是什么？优势？

2. HyperLogLog 作用？优缺点

五、ZSet 有序集合 

1. ZSet 底层是什么结构？

ZSet底层数据结构会根据数据量动态切换，数据量小时使用压缩列表以节省空间。当数据量大时，会自动切换成跳表 （skipList）+ 字典（dict）的双结构。dict根据member直接查score，时间复杂度为O（1），需要查某member对应的score时，直接使用dict查询，跳表是多层索引的有序链表，所有节点保存member + score。按照 score 做升序排序；如果 score 相同，再按照 member 字典序排序。跳表支持范围查询，区间遍历等等。

插入元素时：

同时往skipList和dict中写两份数据，dict维护member和score之间的映射，skipList则使用链表存储<member,score>节点，两份数据虽是冗余，但利用空间换时间还是很高效的。

删除或者更新元素时：二者都要删除更新，保持数据一致。

注意：每个节点插入时层高随机，跳表由多层链表组成，最底层从左到右升序存储了完整数据

为什么跳表的层高随机？

用随机层高模拟平衡，替代红黑树手动旋转，实现简单，不需要复杂平衡逻辑。

2. 为什么 ZSet 用跳表不用红黑树？

两者时间复杂度是同一个级别，增删查都是 O (logN)，性能差距不大，选择跳表主要是实现、范围遍历、内存这几个原因。

范围遍历：

跳表最底层是双向链表，根据起点范围查询更加方便，而红黑树是树形结构，想要顺序遍历需要做中序遍历，递归或者栈去遍历，代码更麻烦，效率也不如直接顺着链表往后走

跳表实现逻辑简单，没有复杂的旋转操作：

红黑树插入删除的时候，为维持平衡，需要做左旋、右旋、变色，逻辑复杂，源码复杂，容易出 bug。 跳表依靠随机生成层高来维持平衡（维持平衡指：跳表的金字塔结构可以快速的缩小范围，保证了查询效率）；插入删除只需要修改前后节点的指针，不需要旋转，代码简单，维护成本低。

内存占用平均下来更低：

红黑树每个节点固定保存左、右、父一共 3 个指针，每个节点开销固定。而跳表每个节点的晋升概率只有1/4，到第二层节点数量就大幅减少，根据数学期望公式 E=1/(1‑p)，p 取 1/4，算出来期望等于 4/3 约等于 1.33，平均层高大约只有 1.33 层，也就是平均每个节点大概只有 1.33 个索引指针。但如果是极端情况，如果一个节点随机到 32 层最高层，那这个节点指针就很多，内存就变大了；只是概率极低。

3. ZSet 的 member 和 score 是否可重复？

member 唯一不可重复；score 可以重复。score 相同时，按 member 字典序排序。

4. ZSet 业务场景？

排行榜、延时队列（没有ack确认，有丢失风险）、热度排榜（score代表热度值）、优先级任务（使用score来明确优先级）。

六、GEO 地理位置 

1. GEO 底层是什么数据结构？

底层是ZSet，用来存经纬度，通过Geohash算法，把二维经纬度变成一维64位的整数（Geohash值），把值作为score存储到Zset中，地理位置名称作为zset的member。利用zset的有序性，score值越接近的代表地理位置越接近，从而可以做附近点的查询。本身不是独立的数据结构，而是基于ZSet封装出来的类型。

2. 为什么 GEO 没有删除命令 GEODEL？怎么删除？

因为底层是 ZSets，没有设置单独命令，直接复用ZSet的删除命令

ZREM key member

3. GEO 的缺点是什么？

1. Geohash 存在精度误差，远距离误差更大；

2. 不支持高精度地理计算；

4. GEO 适用场景？

附近的人、附近门店、骑手定位、周边搜索。

七、Bitmap & HyperLogLog 

1. Bitmap 底层是什么？优势？

底层是 String，操作二进制 bit 位。

极致省内存，1 字节存 8 个状态。适合：签到、活跃状态、布尔标记。

2. HyperLogLog 作用？优缺点

HyperLogLog 是 Redis 的概率型基数统计结构，用来估算去重后的元素个数。 Redis 实现最多占用 12KB 内存，不受元素总量影响； 适合大规模 UV、日活这类粗略去重统计；缺点是结果是近似值，无法取出保存过的原始元素。