1.基本概念

• redis为什么快？

  • 所有操作基于内存，内存访问速度很快
  • 优秀的数据结构

• redis的基本数据结构

  • string

    • string

  • list

    • 压缩列表
    • 双向链表

  • hash\

    • 压缩列表
    • 哈希表

  • set\

    • 哈希表
    • 整数数组

  • zset

    • 压缩列表
    • 跳表

• 问题

  • 键和值之间用什么结构组织
  • 为什么需要这么多数据结构
  • 动态字符串和普通字符串区别

2.redis的数据结构

• redis使用哈希表保存所有键值对（全局hash表）

  • hash表=数组+hash函数

  • hash桶不直接存储元素（因为每个元素大小不相同），存放元素指针

  • key是string指针 value是其他类型指针

  • 优点：

    • 可以用o(1)的时间复杂度找到元素

• 为什么hash表操作变慢

  • hash冲突

    • 通过链地址的方式解决hash冲突（hash桶数量小于元素个数）
    • 缺点 逐渐转成o（n）的操作

  • rehash

    • 当hash冲突过多导致查询速度变慢时，采用rehash扩容数据桶个数

    • redis使用两个hash表，进行渐进式扩容

    • rehash过程

      • 给hash表2分配更大空间
      • 将hash表1数据拷贝到hash表2
      • 释放hash表1的空间

• 渐进式hash

  • 如果一次性解决hash表1数据迁移完，会造成Redis线程阻塞
  • redis正常处理客户端请求，没处理一个请求时从哈希表1中的第一个索引位置拷贝到哈希表2中
  • 没处理一个请求就复制一组hash表到新表中
  • 将一次性大量拷贝的开销分摊到多次处理请求中，保证了不阻塞

3.集合数据操作效率

• string类型操作理想情况下就是o（1）

• 集合操作相对复杂

  • 哈希表比链表实现访问效率高
  • 读写一个元素比读写所有元素效率高

• 有哪些底层数据结构

  • 整数数组

    • 循序读写
    • 通过下标和指针逐个元素访问，操作复杂度O(N)

  • 双向链表

    • 循序读写
    • 通过下标和指针逐个元素访问，操作复杂度O(N)

  • 哈希表

  • 压缩列表

    • 类似一个数组

    • 记录

      • 列表长度
      • 列表尾的偏移量
      • 列表中的 entry 个数

    • 操作

      • 第一个最后一个元素操作是o（1）
      • 其他元素o（n）

  • 跳表

    • 跳表基础上增加多级索引，通过索引位置的跳转，实现数据的快速定位
    • 跳：只在不同的索引表中跳
    • 查找复杂度就是 O(logN)

4.总结

• 使用scan代替大量元素操作
• list适合做pop和push操作，千万不要随机读写