你知道 Redis数据结构底层实现吗？

. 字符串处理(string)

我们都知道redis是用C语言写，但是C语言处理字符串和数组的成本是很高的，下面我分别说几个例子。

没有数据结构支撑的几个问题

1. 及其容易造成缓冲区溢出问题，比如用strcat()，在用这个函数之前必须要先给目标变量分配足够的空间，否则就会溢出。
2. 如果要获取字符串的长度，没有数据结构的支撑，可能就需要遍历，它的复杂度是O(N)
3. 内存重分配。C字符串的每次变更(曾长或缩短)都会对数组作内存重分配。同样，如果是缩短，没有处理好多余的空间，也会造成内存泄漏。

好了，Redis自己构建了一种名叫Simple dynamic string(SDS)的数据结构，他分别对这几个问题作了处理。我们先来看看它的结构源码：

来说说它的优点：

1. 开发者不用担心字符串变更造成的内存溢出问题。
2. 常数时间复杂度获取字符串长度len字段。
3. 空间预分配free字段，会默认留够一定的空间防止多次重分配内存。

这就是string的底层实现，更是redis对所有字符串数据的处理方式(SDS会被嵌套到别的数据结构里使用)。

2. 链表

Redis的链表在双向链表上扩展了头、尾节点、元素数等属性。


 

哈希表的键对泰国或者太少，就需要对哈希表的大小进行调整，redis是如何调整的呢?

我们仔细可以看到dict结构里有个字段dictht ht[2]代表有两个dictht数组。第一步就是为ht[1]哈希表分配空间，大小取决于ht[0]当前使用的情况。

将保存在ht[0]中的数据rehash(重新计算哈希值)到ht[1]上。

当ht[0]中所有键值对都迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并ht[1]初始化，为下一次rehash做准备。

3.3 渐进式rehash

我们在3.2中看到，redis处理rehash的流程，但是更细一点的讲，它如何进行数据迁的呢?

这就涉及到了渐进式rehash，redis考虑到大量数据迁移带来的cpu繁忙(可能导致一段时间内停止服务)，所以采用了渐进式rehash的方案。步骤如下：

为ht[1]分配空间，同时持有两个哈希表(一个空表、一个有数据)。

维持一个技术器rehashidx，初始值0。

每次对字典增删改查，会顺带将ht[0]中的数据迁移到ht[1],rehashidx++(注意：ht[0]中的数据是只减不增的)。

直到rehash操作完成，rehashidx值设为-1。

（编辑：衡水站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!