Reids系列(五)底层数据结构之整数集合

• 前言
• 定义
• 整数集合的升级
  • 整数集合分级的好处
  • 不支持降级
• 总结
• 参考文章
• 联系我

前言

Redis 已经是大家耳熟能详的东西了，日常工作也都在使用，面试中也是高频的会涉及到，那么我们对它究竟了解有多深刻呢？

我读了几本 Redis 相关的书籍，尝试去了解它的具体实现，将一些底层的数据结构及实现原理记录下来。

本文将介绍 Redis 中底层的 intset（整数集合） 的实现方法。 它是 Redis 中集合键的底层实现之一。

2020-01-05-17-31-30

可以看到图中，当我给一个 set 中放入了 5 个数字，此时集合的编码方式是 intset, 而当我放入了一个字符串，编码方式就变成了 hashtable.

定义

intset（整数集合）是 Reids 用于保存整数值的集合抽象数据结构，可以保存 16,31,64 位的整数且保证不重复。

它的结构定义为：

typedef struct intset{
    // 编码方法，指定当前存储的是 16 位，32 位，还是 64 位的整数
    int32 encoding;
    // 集合中的元素数量
    int32 length;
    // 保存元素的数组
    int<T> contents;
}

• encoding 属性有三种取值，分别代表当前整数集合存储方式是用 16 位整数数组，32 位整数数组或者 64 位整数数组。
• length 属性保存了当前整数集合中有多少个整数。
• contents 是一个数组，具体是多少位整数的数组，取决 encoding 的值。

2020-01-05-17-48-00

这是一个保存了 5 个整数的 intset 的结构图。因为存储的数字都很小，所以 encoding 的值是 16 位的整数。

整数集合的升级

是不是很奇怪，整数集合本身就是来存储整数的，为什么还需要编码方式？

因为在 C 语言里，整数也是有很多种的。.

每当一个整数被添加到整数集合时，都需要先去判断 这个整数是否大于 当前编码方式 所能容放的 最大整数, 如果大于，就需要对当前的整数集合进行升级。

升级是指什么呢？假如当前的整数集合中只有一个数字 2. 那么我们用 16 位的整数的数组就可以放下。

当此时进来一个大于 32767(16 位整数的最大值） 的整数，我们就需要将当前的整数数组升级成一个 32 位整数的数组，同时，要将原来的所有整数转换成新的编码。

对于 64 位的升级类似于上面这样。

整数集合分级的好处

1. 用能容纳数字的最小编码进行存储，可以有效的节约内存。
2. 整数集合封装了对三种整数之间的转换，使用我们不用考虑类型错误，可以不断的向整数集合内添加整数。提升了操作的灵活性。

不支持降级

与升级相对应的，当大的数字被删除之后，整数集合不会进行降级。

总结

整数集合时实现集合键的一种数据结构。它以有序数组的实现方式来存储所有的集合元素。

整数集合内部封装了对 16 位，32 位，64 位整数的类型转换，使得整数集合可以灵活的避免类型错误，同时又可以尽量的节约内存，减少用大的数据类型装小的数据的内存浪费。

参考文章

《Redis 的设计与实现（第二版）》

《Redis 深度历险：核心原理和应用实践》

完。 以上皆为个人所思所得，如有错误欢迎评论区指正。

欢迎转载，烦请署名并保留原文链接。

联系邮箱：huyanshi2580@gmail.com

更多学习笔记见个人博客或关注微信公众号 < 呼延十 >