1. 常用数据结构

dict

在redis中最基本的三个数据结构是dict 、adlist和sds,其中dict是redis中最重要的数据结构了,其key-value的映射关系就是通过dict来实现的,dict的内部实现是hash table,这个哈希表的大小是动态增加或减少的,主要是依据哈希表中的元素个数;同时哈希表适用链接法来解决哈希冲突的,具体实现在dict.h和dict.c文件中;

adlist

adlist(a generic doubly linked list)双向链表,这个数据结构在redis中用的也比较多,包括像当前保存的客户端连接或者是value对应是list的实现等,都是用的adlist,这个应该来说比较简单,具体实现在adlist.h和adlist.c;

sds

还有一个比较基本的数据结构就是sds(dynamic string),对字符串处理的简单封装,具体细节实现在sds.h和sds.c中,有一篇文章是介绍sds的实现的,点击这里


2. 支持的数据类型实现

redis作为key-value数据库,value支持的类型比较多,如string, list, set, hash table, zset(有序的集合),下面简单的介绍下内部是如何实现的:

string

string就比较简单了,直接使用前面提到的sds即可,但是这里redis为了保证尽量减少内存的占用,当String代表整数值时,将其转化为long类型来存储,节约内存,具体实现请参考t_string.c文件;

list

list类型的实现使用了两种数据结构adlist和ziplist,所在文件t_list.c

  • ziplist: 当list的数据量< 配置文件list-max-ziplist-entries && list中元素的大小 <list-max-ziplist-value 时,list采用这种数据结构,这样做一方面为了节省内存,另一方面这种结构式顺序存储的结构,能够更好利用cpu local和预取策略,具体实现在ziplist.c中
  • adlist: 使用前文提到的双向链表结构,这里不再赘述

set

set的实现也是使用两种类型的数据结构,所在文件t_set.c

  • intset: 当集合中的元素为整数时,使用intset数据结构,内部实现就是一个整数数组,数组是有序的,具体实现请参考intset.h和intset.c文件
  • dict: 当集合中元素包括字符串时,必须将其转化为dict结构,key为元素值,value为NULL,这样即可在O(1)时间内判断集合中是否包含某个元素

hash table

hash table的实现也会用到两种数据结构,所在文件t_hash.c

  • zipmap: 使用这种结构的原因与ziplist的原因类似,节省内存,具体实现在zipmap.h和zipmap.c
  • dict:  前面已经介绍过,不再赘述

zset

zset有序集合,也会用到两种数据结构skip list 和dict,请参考我的上一篇blog 实现在t_zset.c中

通过看redis源码,发现其在内存优化方面确实做了不少工作,有很多可以学习的地方的~先写到这里吧。

来自yaronspace.cn  本文链接:http://yaronspace.cn/blog/archives/1263