关于Redis底层的两个问题
1. 为什么Redis不共享包含字符串的对象?
当服务器考虑将一个共享对象设置为键的值对象时,程序首先需要检查给定的共享对象和键想要创建的目标对象是否完全相同,只有在共享对象和目标对象完全相同的情况下,程序才会将共享对象用作键的值对象,而一个共享对象保存的值越复杂,验证共享对象和目标对象是否相同所需的复杂度就越高,消耗的CPU时间也越多:
- 如果共享对象是保存整数值的字符串对象,那么验证操作的复杂度为O(1);
- 如果共享对象是保存字符串值的字符串对象,那么验证操作的复杂度为O(N);
- 如果共享对象是保存了多个值(或者对象)的对象,如果列表对象或者哈希对象,那么验证操作的复杂度将会是O(N^2);
因此,尽管共享更复杂的对象是可以节约更多的内存,但受到CPU时间的限制,Redis只对白喊整数值的字符串对象进行共享。
2. 为什么有序集合需要同时使用跳跃表和字典来实现?
在理论上,有续集和可以单独使用字典或者跳跃表的其中一种数据结构来实现,但是无论单独使用字典还是跳跃表,在性能上对比起同时使用字典和跳跃表都会有所降低。
举个例子:如果我们只是使用字典来实现有序集合,那么虽然以O(1)复杂度查找成员的分值这一特性会被保留,但是因为字典以无序的方式来保存集合元素,所以每次在执行范围型操作——比如ZRANK、ZRANGE等命令时,程序都需要对字典保存的所有元素进行排序,完成这种排序至少需要O(NlogN)时间复杂度,以及额外的O(N)空间复杂度(因为要创建一个数组来保存排序后的元素)。
另一方面,如果我们只使用跳跃表来实现有序集合,那么跳跃表执行范围型操作的所有优点都会被保留,但是因为没有了字典,所以根据成员查找分值这一操作的复杂度将从O(1)上升到O(logN)。
以为以上原因,为了让有序集合的查找的范围型操作都尽可能快地执行,Redis选择了同时使用字典和跳跃表两种数据结构来实现有序集合。