数据结构

Redis中包含的数据类型

  • String(字符串)、List(列表)、Hash(哈希)、Set(集合)、Sorted Set(有序集合)

image-20210826101459882

问题：

  1. 这些数据结构都是值的底层实现，键和值本⾝之间⽤什么结构组织？

    • 给哈希表2分配更⼤的空间，例如是当前哈希表1⼤⼩的两倍

    • 把哈希表1中的数据重新映射并拷⻉到哈希表2中

    • 释放哈希表1的空间

    这个过程看似简单，但是第⼆步涉及⼤量的数据拷⻉，如果⼀次性把哈希表1中的数据都迁移完，会造成Redis线程阻塞，⽆法服务其他请求。此时，Redis就⽆法快速访问数据了。 为了避免这个问题，Redis采⽤了渐进式rehash。

    简单来说就是在第⼆步拷⻉数据时，Redis仍然正常处理客⼾端请求，每处理⼀个请求时，从哈希表1中的第⼀个索引位置开始，顺带着将这个索引位置上的所有entries拷⻉到哈希表2中；等处理下⼀个请求时，再顺带拷⻉哈希表1中的下⼀个索引位置的entries

    image-20210826151935525

  2. 为什么集合类型有那么多的底层结构，它们都是怎么组织数据的，都很快吗？

    集合类型的底层数据结构主要有5种：整数数组、双向链表、哈希表、压缩列表和 跳表。

    压缩列表实际上类似于⼀个数组，数组中的每⼀个元素都对应保存⼀个数据。和数组不同的是，压缩列表在 表头有三个字段zlbytes、zltail和zllen，分别表⽰列表⻓度、列表尾的偏移量和列表中的entry个数；压缩列 表在表尾还有⼀个zlend，表⽰列表结束。

    image-20210826154149881

    在压缩列表中，如果我们要查找定位第⼀个元素和最后⼀个元素，可以通过表头三个字段的⻓度直接定位，复杂度是O(1)。⽽查找其他元素时，就没有这么⾼效了，只能逐个查找，此时的复杂度就是O(N)了

    跳表：有序链表只能逐⼀查找元素，导致操作起来⾮常缓慢，于是就出现了跳表。具体来说，跳表在链表的基础上，增加了多级索引，，通过索引位置的⼏个跳转，实现数据的快速定位，当数据量很⼤时，跳表的查找复杂度就是O(logN)。

    image-20210826154704451 image-20210826155137460

  3. 什么是简单动态字符串，和常⽤的字符串是⼀回事吗？