面试重要程度：⭐⭐⭐⭐⭐

常见提问方式： Redis底层实现、跳跃表原理、压缩列表优化

预计阅读时间：45分钟

🎯 String、Hash、List、Set、ZSet底层实现

String类型底层实现

面试官： "Redis的String类型底层是如何实现的？"

必答要点：

SDS（Simple Dynamic String）结构：

// Redis 6.0+ SDS结构
struct sdshdr8 {
    uint8_t len;        // 已使用长度
    uint8_t alloc;      // 总分配长度
    unsigned char flags; // 类型标识
    char buf[];         // 字符数组
};

// SDS相比C字符串的优势：
/**
 * 1. O(1)获取字符串长度（len字段）
 * 2. 杜绝缓冲区溢出（alloc字段控制）
 * 3. 减少修改字符串时的内存重分配次数
 * 4. 二进制安全（可存储任意数据）
 * 5. 兼容部分C字符串函数
 */

String类型编码方式：

/**
 * String类型的三种编码
 */
public class RedisStringEncoding {
    
    /**
     * 1. REDIS_ENCODING_INT
     * 条件：字符串是整数且在long范围内
     * 优势：节省内存，整数运算更快
     */
    public void intEncoding() {
        // SET counter 100
        // 存储为long类型，占用8字节
        jedis.set("counter", "100");
        jedis.incr("counter");  // 直接进行整数运算
    }
    
    /**
     * 2. REDIS_ENCODING_EMBSTR  
     * 条件：字符串长度 <= 44字节（Redis 6.0）
     * 优势：RedisObject和SDS在连续内存中，减少内存碎片
     */
    public void embstrEncoding() {
        // SET name "张三"
        // RedisObject和SDS一次分配，提高缓存局部性
        jedis.set("name", "张三");
    }
    
    /**
     * 3. REDIS_ENCODING_RAW
     * 条件：字符串长度 > 44字节
     * 特点：RedisObject和SDS分别分配内存
     */
    public void rawEncoding() {
        // SET description "很长的描述信息..."
        String longStr = "很长的描述信息".repeat(20);
        jedis.set("description", longStr);
    }
}

Hash类型底层实现

Hash类型的两种编码：

/**
 * Hash类型编码转换
 */
public class RedisHashEncoding {
    
    /**
     * 1. REDIS_ENCODING_ZIPLIST（压缩列表）
     * 条件：
     * - 所有键值对的键和值字符串长度都小于64字节
     * - 键值对数量少于512个
     */
    public void ziplistEncoding() {
        // HSET user:1 name "张三" age "25" city "北京"
        Map<String, String> user = new HashMap<>();
        user.put("name", "张三");
        user.put("age", "25");
        user.put("city", "北京");
        jedis.hmset("user:1", user);
        
        // 内存布局紧凑，节省空间
        // 但查找时间复杂度为O(n)
    }
    
    /**
     * 2. REDIS_ENCODING_HT（哈希表）
     * 条件：不满足ziplist条件时自动转换
     */
    public void hashtableEncoding() {
        // 当键值对数量或长度超过阈值时转换
        Map<String, String> largeUser = new HashMap<>();
        for (int i = 0; i < 600; i++) {
            largeUser.put("field" + i, "value" + i);
        }
        jedis.hmset("user:large", largeUser);
        
        // 查找时间复杂度为O(1)
        // 但内存开销较大
    }
}

List类型底层实现

List类型编码演进：

/**
 * List类型编码（Redis版本演进）
 */
public class RedisListEncoding {
    
    /**
     * Redis 3.0之前：ZIPLIST + LINKEDLIST
     */
    public void oldEncoding() {
        // 小数据量：ZIPLIST（压缩列表）
        // 大数据量：LINKEDLIST（双向链表）
        
        // 问题：两种数据结构差异大，维护复杂
    }
    
    /**
     * Redis 3.2+：QUICKLIST
     * 结合了ziplist和linkedlist的优点
     */
    public void quicklistEncoding() {
        // LPUSH mylist "a" "b" "c"
        jedis.lpush("mylist", "a", "b", "c");
        
        /**
         * QuickList结构：
         * - 由多个ziplist节点组成的双向链表
         * - 每个节点是一个ziplist
         * - 平衡了内存使用和操作效率
         */
    }
}

QuickList结构详解：

// QuickList节点结构
typedef struct quicklistNode {
    struct quicklistNode *prev;    // 前驱节点
    struct quicklistNode *next;    // 后继节点
    unsigned char *zl;             // ziplist指针
    unsigned int sz;               // ziplist字节数
    unsigned int count : 16;       // ziplist中元素个数
    unsigned int encoding : 2;     // 编码方式
    unsigned int container : 2;    // 容器类型
    unsigned int recompress : 1;   // 是否压缩
    unsigned int attempted_compress : 1; // 压缩尝试标志
    unsigned int extra : 10;       // 预留字段
} quicklistNode;

// QuickList主结构
typedef struct quicklist {
    quicklistNode *head;           // 头节点
    quicklistNode *tail;           // 尾节点
    unsigned long count;           // 总元素数量
    unsigned long len;             // 节点数量
    int fill : QL_FILL_BITS;      // 每个节点的填充因子
    unsigned int compress : QL_COMP_BITS; // 压缩深度
} quicklist;

Set类型底层实现

/**
 * Set类型的两种编码
 */
public class RedisSetEncoding {
    
    /**
     * 1. REDIS_ENCODING_INTSET（整数集合）
     * 条件：
     * - 所有元素都是整数
     * - 元素数量不超过512个
     */
    public void intsetEncoding() {
        // SADD numbers 1 2 3 4 5
        jedis.sadd("numbers", "1", "2", "3", "4", "5");
        
        /**
         * IntSet特点：
         * - 有序存储（便于二分查找）
         * - 根据整数范围选择编码（int16/int32/int64）
         * - 内存紧凑，查找效率O(log n)
         */
    }
    
    /**
     * 2. REDIS_ENCODING_HT（哈希表）
     * 条件：不满足intset条件时转换
     */
    public void hashtableEncoding() {
        // SADD tags "java" "redis" "mysql" "spring"
        jedis.sadd("tags", "java", "redis", "mysql", "spring");
        
        // 查找、插入、删除都是O(1)
        // 但内存开销较大
    }
}

ZSet类型底层实现

面试官： "有序集合ZSet是如何实现的？跳跃表的原理是什么？"

ZSet的两种编码：

/**
 * ZSet类型编码
 */
public class RedisZSetEncoding {
    
    /**
     * 1. REDIS_ENCODING_ZIPLIST
     * 条件：
     * - 元素数量少于128个
     * - 所有member长度小于64字节
     */
    public void ziplistEncoding() {
        // ZADD leaderboard 100 "player1" 200 "player2"
        Map<String, Double> scores = new HashMap<>();
        scores.put("player1", 100.0);
        scores.put("player2", 200.0);
        jedis.zadd("leaderboard", scores);
        
        // 在ziplist中按score排序存储
        // member和score紧挨着存储
    }
    
    /**
     * 2. REDIS_ENCODING_SKIPLIST + HASH
     * 条件：不满足ziplist条件时转换
     * 同时使用跳跃表和哈希表
     */
    public void skiplistEncoding() {
        Map<String, Double> largeScores = new HashMap<>();
        for (int i = 0; i < 200; i++) {
            largeScores.put("player" + i, Math.random() * 1000);
        }
        jedis.zadd("large_leaderboard", largeScores);
        
        /**
         * 数据结构组合：
         * - SkipList：支持范围查询，O(log n)
         * - HashMap：支持O(1)的member查找
         */
    }
}

🚀 跳跃表与压缩列表深度解析

跳跃表（Skip List）原理

跳跃表结构：

// 跳跃表节点
typedef struct zskiplistNode {
    sds ele;                        // member对象
    double score;                   // 分值
    struct zskiplistNode *backward; // 后退指针
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span;            // 跨度
    } level[];                      // 层级数组
} zskiplistNode;

// 跳跃表主结构
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 头尾指针
    unsigned long length;                 // 节点数量
    int level;                           // 最大层数
} zskiplist;

跳跃表查找过程：

/**
 * 跳跃表查找算法模拟
 */
public class SkipListSearch {
    
    /**
     * 查找score=60的元素
     * 
     * 层级结构示例：
     * L3: 1 ---------> 50 ---------> 100
     * L2: 1 -> 20 ---> 50 -> 70 ---> 100
     * L1: 1 -> 20 -> 30 -> 50 -> 60 -> 70 -> 80 -> 100
     */
    public void searchProcess() {
        // 从最高层开始查找
        // L3: 1 -> 50，50 < 60，继续向前
        // L3: 50 -> 100，100 > 60，下降到L2
        
        // L2: 50 -> 70，70 > 60，下降到L1
        
        // L1: 50 -> 60，找到目标
        
        /**
         * 时间复杂度分析：
         * - 平均情况：O(log n)
         * - 最坏情况：O(n)（退化为链表）
         * - 空间复杂度：O(n)
         */
    }
}

跳跃表vs其他数据结构：

/**
 * 数据结构对比
 */
public class DataStructureComparison {
    
    public void comparison() {
        /**
         * 跳跃表 vs 平衡二叉树：
         * 
         * 跳跃表优势：
         * 1. 实现简单，无需复杂的旋转操作
         * 2. 范围查询效率高（有序链表特性）
         * 3. 并发友好，锁粒度小
         * 4. 内存局部性好
         * 
         * 平衡二叉树优势：
         * 1. 最坏情况性能保证O(log n)
         * 2. 内存使用更少（无冗余指针）
         */
        
        /**
         * Redis选择跳跃表的原因：
         * 1. 实现简单，代码维护成本低
         * 2. 支持高效的范围查询（ZRANGE命令）
         * 3. 平均性能接近平衡树
         * 4. 适合内存数据库的场景
         */
    }
}

压缩列表（ZipList）原理

压缩列表结构：

// ZipList整体结构
// <zlbytes><zltail><zllen><entry1><entry2>...<entryN><zlend>

typedef struct zlentry {
    unsigned int prevrawlensize; // 前一个entry长度所需字节数
    unsigned int prevrawlen;     // 前一个entry的长度
    unsigned int lensize;        // 当前entry长度所需字节数
    unsigned int len;            // 当前entry的长度
    unsigned int headersize;     // header大小
    unsigned char encoding;      // 编码类型
    unsigned char *p;           // 指向entry的指针
} zlentry;

压缩列表优化原理：

/**
 * 压缩列表内存优化
 */
public class ZipListOptimization {
    
    public void memoryOptimization() {
        /**
         * 内存节省策略：
         * 
         * 1. 紧凑存储：
         * - 连续内存分配，无内存碎片
         * - 无指针开销（普通链表每个节点需要前后指针）
         * 
         * 2. 变长编码：
         * - 根据数据大小选择最小的存储方式
         * - 整数：1/2/4/8字节编码
         * - 字符串：根据长度选择1/2/5字节长度前缀
         * 
         * 3. 特殊编码：
         * - 小整数直接编码在type字段中
         * - 短字符串优化存储
         */
    }
    
    public void cascadeUpdate() {
        /**
         * 连锁更新问题：
         * 
         * 场景：插入一个元素导致后续元素的prevlen字段需要扩展
         * 
         * 例如：
         * - 原来prevlen用1字节存储（< 254）
         * - 插入大元素后，prevlen需要5字节存储
         * - 可能引发连锁反应，多个元素需要重新编码
         * 
         * 解决：
         * - Redis会尽量避免这种情况
         * - 当ziplist过大时转换为其他数据结构
         */
    }
}

🔧 Redis内存优化实战

数据结构选择策略

/**
 * Redis数据结构选择指南
 */
@Service
public class RedisOptimizationService {
    
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    
    /**
     * 小对象存储优化
     */
    public void smallObjectOptimization() {
        // ✅ 使用Hash存储小对象（利用ziplist编码）
        Map<String, String> user = new HashMap<>();
        user.put("id", "1001");
        user.put("name", "张三");
        user.put("age", "25");
        redisTemplate.opsForHash().putAll("user:1001", user);
        
        // ❌ 避免为每个字段单独设置key
        // redisTemplate.opsForValue().set("user:1001:id", "1001");
        // redisTemplate.opsForValue().set("user:1001:name", "张三");
        // redisTemplate.opsForValue().set("user:1001:age", "25");
    }
    
    /**
     * 列表数据优化
     */
    public void listOptimization() {
        // ✅ 小列表使用List（quicklist编码）
        List<String> tags = Arrays.asList("java", "redis", "spring");
        redisTemplate.opsForList().leftPushAll("user:1001:tags", tags);
        
        // ✅ 大列表考虑分片
        for (int i = 0; i < 10000; i++) {
            int shardId = i % 10;  // 分成10个分片
            redisTemplate.opsForList().leftPush("large_list:" + shardId, "item" + i);
        }
    }
    
    /**
     * 有序集合优化
     */
    public void zsetOptimization() {
        // ✅ 小数据量使用ZSet（ziplist编码）
        ZSetOperations<String, Object> zset = redisTemplate.opsForZSet();
        zset.add("small_rank", "player1", 100);
        zset.add("small_rank", "player2", 200);
        
        // ✅ 大数据量考虑分桶
        long userId = 1001L;
        int bucket = (int) (userId % 100);  // 分成100个桶
        zset.add("rank_bucket:" + bucket, "user:" + userId, 500);
    }
}

内存使用监控

/**
 * Redis内存监控
 */
@Component
public class RedisMemoryMonitor {
    
    @Autowired
    private RedisTemplate<String, Object> redisTemplate;
    
    /**
     * 获取内存使用情况
     */
    public void memoryInfo() {
        Properties info = redisTemplate.getConnectionFactory()
            .getConnection().info("memory");
        
        /**
         * 关键指标：
         * used_memory: 已使用内存
         * used_memory_human: 人类可读格式
         * used_memory_rss: 系统分配的物理内存
         * used_memory_peak: 内存使用峰值
         * mem_fragmentation_ratio: 内存碎片率
         */
        
        String usedMemory = info.getProperty("used_memory_human");
        String fragmentation = info.getProperty("mem_fragmentation_ratio");
        
        System.out.println("已使用内存: " + usedMemory);
        System.out.println("内存碎片率: " + fragmentation);
    }
    
    /**
     * 分析key的内存使用
     */
    public void analyzeKeyMemory() {
        // 使用MEMORY USAGE命令（Redis 4.0+）
        RedisConnection connection = redisTemplate.getConnectionFactory().getConnection();
        
        String[] keys = {"user:1001", "large_list:0", "small_rank"};
        for (String key : keys) {
            Long memoryUsage = connection.memoryUsage(key.getBytes());
            System.out.println(key + " 内存使用: " + memoryUsage + " bytes");
        }
    }
}

💡 面试回答要点

标准回答模板

数据结构底层实现：

"Redis的五种数据类型都有多种底层编码实现：

String类型：int、embstr、raw三种编码，根据内容和长度自动选择
Hash类型：ziplist和hashtable，小数据用ziplist节省内存
List类型：使用quicklist，结合了ziplist和linkedlist的优点
Set类型：intset和hashtable，整数集合用intset优化
ZSet类型：ziplist和skiplist+hash，跳跃表支持高效范围查询

这种设计在保证功能的同时，针对不同场景进行了内存和性能优化。"

跳跃表原理：

"跳跃表是一种概率性数据结构，通过多层索引实现O(log n)的查找效率。
相比平衡二叉树，跳跃表实现简单，支持高效的范围查询，
内存局部性好，适合Redis的内存数据库场景。
Redis在ZSet中使用跳跃表配合哈希表，
既支持按score范围查询，又支持按member快速查找。"

本节核心要点：

• ✅ 五种数据类型的底层编码实现
• ✅ 跳跃表和压缩列表的原理和优化
• ✅ 内存使用优化策略和监控方法
• ✅ 数据结构选择的最佳实践

总结： 深入理解Redis数据结构的底层实现，有助于在实际项目中做出正确的数据结构选择，优化内存使用和查询性能