从redis谈数据结构

     说到redis,最近可是挺火的呀,越来越多的互联网公司都开始使用了,所以我最近也研究了一下,顺带把我的理解写下来,如果有什么问题的话,请指正.

 

首先redis相比memcache一个很不一样的一点就是支持一些复杂的数据结构,比如list,set ,sorted set,hash等,所以我们就先从这些数据结构入手,进行讲解

 

1.list 列表

这个是一个非常常见的数据,相应的实现也有多种,比较常见的是基于数组和基于链表的(比如java中的ArrayList和LinkedList)

那我们先了解到最开始的两个数据结构了

数组:别告诉我这个你不懂 ,new String[3]这样的用过吧??这个结构最简单了

这个结构有个好处就是通过索引来定位数据非常快,但是呢,增加,删除数据的时候就麻烦了,需要移动大量的指针,就好比排队买枣糕王,前面的人买好走了,那是不是大家都要移动??而且我们查找人的时候经常还会需要根据具体的值来查找,比如排队的时候,我们要找具体某个人,我们一般不会知道它在队列中的索引,而只知道TA的名字,这个时候,就需要遍历整个队列来寻找了(众人:你不会叫名字呀???不是一下就找到了?? 我: -_-!!! 数组中的数据也这么智能的话可以考虑...)

于是,下面这位同学登场了

链表:为了简单,我就拿单向链表举例,大概就是长这个样子(一图胜千言):

      

 

 

     上面这个图不知道大家看懂没(画图是我的硬伤.....),不过这个链表相比数组肯定是复杂了一些,但是也带来了一些好处,就是我们修改的时候方便了,在我们增加和删除节点的时候,只需要改一下链接就行了,时间复杂度为o(1) .什么??你不懂啥叫时间复杂度... 

     好吧,我简单介绍下啥叫时间复杂度,首先时间复杂度一般涉及查找和修改(添加,删除)的时间复杂度.简单你可以理解为CPU在处理你的查找或者修改的时候需要执行的时间度量.举个例子吧,比如刚才的数组,你如果要根据值查找的话,需要遍历整个数组(假设数组长度为n)来寻找,那就是让CPU去运行n次对比的操作(虽然实际对比次数<=n),那我们就说查找的时间复杂度是o(n),插入和删除的时候我们也可能移动n个数据的位置,所以修改的时间复杂度也是o(n),也就是说,这里的时间复杂度只是一个大体的估计,或者说叫一个时间的数量级吧.

     了解了时间复杂度,就可以知道链表增加和删除节点的代价是很小的,但是,查找数据怎么办呢??还是o(n)的复杂度呀?这个问题等下我再回答,因为这里讨论的是list的实现,用这里的知识就可以了

     redis中list的实现有两种,一种是ziplist,还有一种就是linkedlist,ziplist我就不介绍了,就是linkedlist的一种优化,这里主要讲解的是linkedlist,这里使用的是双向链表,和单向链表不同的地方就是多了一个指针指向前一个节点,这样可以方便的进行逆向的遍历

     既然list是用双向链表实现的,那就会有链表的特点,可以看到lpush的时间复杂度为o(1),而查找比较慢,比如根据数值删除的操作lrem复杂度为o(n)

 

2.set 无序集合

     说到set,在java中,大家用的最多的应该是hashset吧,其实hashset就是更加常用的hashmap实现的,而redis中的set实现有两种,一种是intset,还有一种是hashtable实现的set,intset算是一种特定的优化版本,在数据量小,并且set中是数值的时候,会使用,如果超过了一定量(set_max_intset_entries参数指定,默认512),就会变成hashtable版本的,而intset实际上就是普通的数组结构,所以接下来主要介绍的还是hashtable的实现

     hashtable(哈希表)就是为了解决我们刚才说的查找数据慢产生的,大体上是由hash算法 + 数组 + 链表实现的(听起来就感觉比较强大吧^^),简单的说,就是把需要存储的数据先均匀的进行分组(hash + 数组),之后,数组中存储的元素是一个链表,链表中将相同hash值的元素串起来,这样在进行搜索的时候,就可以通过hash迅速的定位到数据了,所以我们看到sismember的时间复杂度是o(1),而且由于元素以链表进行组织,修改的时间复杂度也是o(1),哈哈,多么强大的数据结构呀,这似乎已经完美了......但是,我们忘了重要的一点,它是无序的,所以我们还需要下面这个数据结构来做支撑.

 

3.sorted set 有序集合

     说到排序,这个也算是算法中很重要的一部分了,还记得那些冒泡,快速,选择排序等么,这些都是为了提高排序的速度产生的,但是它们是基于已经存在的数组,而我们这里的排序是数据在进行修改的时候进行的,也就是说,你添加和删除元素的时候,就保证了数据是有序的了,而且你还需要保证查找的速度够快,这个可不是一个简单的问题,为了让这几个条件都满足,各种数据结构都出现了(所以也就没那么简单了),比如数据库和文件系统中常用的B+tree,还有常见的平衡二叉树--红黑树,还有我们就是redis的sorted set的实现--skiplist,也许你会问为啥不用红黑树,我觉得是因为实现难易程度的原因,skiplist实现起来比较简单,而且各方面性能和红黑树差不多,查找,修改的复杂度都为log(n) (指数为2).

     redis中的sorted set其实并不是简单的由skiplist实现的,它还使用了一个hashtable来存储 数据与score的映射(这里提一个疑问,不知道为啥,redis的作者把zskiplist的定义写在了redis.h中,而没有单独放到一个文件里),实际上skiplist中已经存储了score了,把数据做冗余应该是为了提高查询的速度.

     

     今天就写到这里吧,其实之前总是觉得java程序员好像不需要学习数据结构,算法这些吧,但是最近渐渐的发现,其实这些都是基础,不管是学习什么语言都应该掌握,可能我们不会自己去实现这些数据结构和算法,但是了解了这些,你才能更好的去使用基于这些基础搭建起来的软件,才能使用的更加得心应手^^

 

 

 

评论

2 楼 zh_harry 2013-07-23  

redis我挺熟的，不要脸一把

1 楼 sharewind 2013-03-18  

牛人啊，膜拜一下