Redis数据库学习

字典

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

图中有两个哈希表， 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使用跳跃表作为有序集合键的底层实现之一。

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

表头（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个子节点。
• 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。
• 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。

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

参考

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