极客时间-Redis核心技术与实战笔记(2)

本文主要是介绍极客时间-Redis核心技术与实战笔记(2)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

首先老师提出一个问题：Redis的快，快在哪里？

1. 内存数据库，所有操作在内存完成。
2. 键值对使用的高效的数据结构。

老师用了一张图详细的展示了Redis的不同类型的数据底层所用的数据结构：
上述数据结构都是值的底层实现。

键和值用什么结构组织：

使用哈希表（一个数组）保存所有键值对。
值是集合类型如何保存？
哈希表中保存指向具体值的指针。

使用哈希表可以用O(1)时间复杂度快速查找到键值对。
潜在风险：hash冲突，rehash可能的操作阻塞。
解决hash冲突：
链式hash。

链式hash存在的问题：
随着存入数据量的增大，每一个哈希桶的哈希冲突链过长，导致查找耗时长。

解决链式hash存在的问题：
rehash：增加现有哈希桶数量数据更加分散的保存。
rehash机制: 两个全局哈希表，默认使用哈希表1，随着数据逐步增多：

1. 分配哈希表1一定倍数的空间给哈希表2。
2. 哈希表1数据拷贝到哈希表2。
3. 释放哈希表1空间。

rehash机制存在的问题：
数据从哈希表1一次性迁入哈希表2涉及大量数据拷贝造成线程阻塞。无法服务其他请求。

解决rehash机制存在问题：
渐进式Rehash。
每处理一个请求时，将请求对应的第一个哈希表位置所有数据拷贝到第二个表。将一次性大量拷贝开销分摊到多次请求处理。

集合数据操作效率：

集合数据操作效率与哪些因素有关？

1. 集合数据所用数据结构。哈希表>链表。
2. 执行的具体操作，读写一个元素与读写所有元素。

哈希表：O(1)
整数数组和双向链表：O(n)。数组查询需要遍历，直接访问才是O(1)
压缩列表：通过表头表尾字段直接定位：O(1)，查找其他元素：O(n)。

为什么要设计压缩列表？
减少内存的使用和碎片化，使得数据结构化的无用的信息减少。压缩列表中每个节点的len属性使得压缩列表可以存放不同大小的数据并实现双向遍历。

解决逐一查找元素效率低的问题：
跳表：在链表基础上增加多级索引。通过几次跳转实现数据的快速定位。（空间换时间）
时间复杂度O(logn)

不同操作的复杂度：

单元素操作：操作的复杂度由集合采用的数据结构决定。
范围操作：返回一个范围中的数据。O(n)。

避免一次返回所有元素导致阻塞：渐进式遍历，每次只返回有限数据。

统计操作：集合类型对集合中所有元素个数记录。O(1)。

这篇关于极客时间-Redis核心技术与实战笔记(2)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！