Redis数据库学习

栏目: 数据库 · 发布时间: 5年前

内容简介:图中有两个哈希表,渐进式rehash的好处在于它采取分而治之的方式,将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,因为rehash的过程中同时有两个哈希表存在,所以在此期间字典的删除、查找、更新操作都会在两个哈希表上进行,例如在字典中查找一个键,程序会先在跳跃表是一种有序数据结构,他通过在每个节点中维护多个指向其他节点的指针,从而达到快速访问节点的目的。 跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。在大部分情况下, 跳

字典

Redis数据库的底层实现使用的是字典数据结构,对数据库的增、删、查、改都是在对字典进行操作。 其底层实现是哈希表,每个哈希槽存放键和值两个数据,使用链表来处理哈希冲突。哈希算法使用的是MurmurHash2算法。如下图:

Redis数据库学习

图中有两个哈希表, ht[1] 主要是在rehash的时候当作过渡用,Redis的rehash是渐进式进行的,不是一次性完成rehash,这样做是为了避免当哈希值比较多时一次性rehash会导致服务器在一段时间内停止服务。渐进式rehash的详细过程:

  1. ht[1] 分配空间,让字典同时持有 ht[0]ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx ,并将他的值设置为0,表示rehash工作正式开始。
  3. 在rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对rehash到 ht[1] ,当rehash工作完成之后,程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行,最终在某个时间点上, ht[0] 的所有键值对都会被rehash到 ht[1] ,这时程序将 rehashidx 属性值设为-1,表示rehash操作已完成。

渐进式rehash的好处在于它采取分而治之的方式,将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,因为rehash的过程中同时有两个哈希表存在,所以在此期间字典的删除、查找、更新操作都会在两个哈希表上进行,例如在字典中查找一个键,程序会先在 ht[0] 里面查找,如果没有找到则继续在 ht[1] 中查找。但是在添加键值对操作时新的键值对会一律保存到 ht[1] 里面,不会对 ht[0] 做任何添加操作,这是为了保证 ht[0] 键值对的数量只能减少不能增加。

跳跃表

跳跃表是一种有序数据结构,他通过在每个节点中维护多个指向其他节点的指针,从而达到快速访问节点的目的。 跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。在大部分情况下, 跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树更为简单,所以可以使用跳跃表来代替平衡树。 Redis使用跳跃表作为有序集合键的底层实现之一。

Redis数据库学习

跳跃表主要由以下部分构成:

表头(head):负责维护跳跃表的节点指针。

跳跃表节点:保存着元素值,以及多个层。

层:保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率, 程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。(层的高度是随机生成的)

表尾:全部由 NULL 组成,表示跳跃表的末尾。

具体查找、插入、删除过程参考 浅析SkipList跳跃表原理及代码实现

过期键删除策略

Redis允许使用EXPIREAT命令或PEXPIREAT命令,以秒或者毫秒精度给数据库中的某个键设置过期时间。 expires字典保存了数据库中所有键的过期时间,我们称这个字典为过期字典:

  • 过期字典的键是一个指针,这个指针指向键空间中的某个键对象。
  • 过期字典的值是一个long long类型的整数,这个整数保存了键所指向的数据库键的过期时间,一个毫秒精度的UNIX时间戳。

Redis有两种删除策略:

  1. 惰性删除策略

惰性删除策略是在所有读写数据库的 Redis 命令执行之前都会调用 expireIfNeeded 函数对输入键进行检查:

expireIfNeeded
expireIfNeeded

expireIfNeeded 函数就像一个过滤器,它可以在命令真正执行之前,过滤掉过期的输入键,从而避免命令接触到过期键。

  1. 定期删除策略

定期删除策略就是定期遍历数据库,判断是否过期,如果过期就删除对应的键值对。Redis中不是一次性遍历整个数据库, 而是在规定的时间内分多次遍历服务器中的各个数据库,每次遍历检查一部分键的过期时间。

关系型数据库中的索引数据结构B+Tree

B+树的定义:

  • 一个节点可以容纳多个值。
  • 除非数据已经填满,否则不会增加新的层。也就是说,B树追求”层”越少越好。
  • 子节点中的值,与父节点中的值,有严格的大小对应关系。一般来说,如果父节点有a个值,那么就有a+1个子节点。
  • 所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。
  • 所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。

Redis数据库学习

关系型数据库为什么要使用B+Tree作为索引,主要目的是为了减少磁盘的读取次数,B+树的每个节点存储了大量的索引信息(每个节点就相当于一个磁盘块), 所以查找一条数据记录只需要读取少量节点就可以找到数据的位置。

参考

本篇文章主要是读《redis设计与实现 第二版》这本书的读书笔记。打算好好看看数据库相关的知识,对数据库一直很陌生。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

人月神话

人月神话

[美] 弗雷德里克·布鲁克斯 / 汪颖 / 清华大学出版社 / 2002-11 / 29.80元

作者为人们管理复杂项目提供了颇具洞察力的见解,既有很多发人深省的观点,也有大量的软件工程实践。书中的内容来自布鲁克斯在IBM公司System 360家族和OS 360中的项目管理经验。初版的20年后,布鲁克斯重新审视了他原先的观点,增加了一些新的想法和建议。新增加的章节包括:原著中一些核心观点的精华;在经过了一个时代以后,Brooks博士对原先观点新的认识;1986年的经典文章《没有银弹》;对19......一起来看看 《人月神话》 这本书的介绍吧!

MD5 加密
MD5 加密

MD5 加密工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具