Redis数据结构

Redis数据类型及底层数据结构

• String(字符串)：动态字符串 O(1)
• List(列表)：双向链表，压缩列表
• Hash(哈希)：哈希表，压缩列表
• Set(集合)：哈希表，整数数组
• Sorted Set(有序集合)：跳表，压缩列表

Redis键值结构

全局哈希表，实现从键到值的快速访问 写入大量数据变慢：哈希冲突、rehash

• 哈希表 O(1) String
• 整数数组和双向链表 O(n)
• 压缩列表 zlbytes|zltail|zllen|entry1|entry2|..|entryN|zlend O(n)
• 跳表 在链表基础上增加多级索引，实现快速定位 O(logN)

Redis操作复杂度总结

• 单元素操作是基础 O(1)
• 范围操作非常耗时 O(N)
• 统计操作非常高效 O(1)
• List头尾操作 O(1)