NOSQL和Redis五大数据结构入门

从今天开始学习非关系型数据库即NOSQL(Not Only SQL),而Redis则是著名的NOSQL数据库之一,今天来学习NOSQL的五大数据结构并对五大数据结构进行总结,在这之前,先了解了解非关系型数据库NOSQL。

关于NOSQL

什么是NOSQL

NoSQL(NoSQL = Not Only SQL ),意即”不仅仅是SQL”。在现代的计算系统上每天网络上都会产生庞大的数据量。这些数据有很大一部分是由关系数据库管理系统(RDBMS)来处理。 1970年 E.F.Codd’s提出的关系模型的论文 “A relational model of data for large shared data banks”,这使得数据建模和应用程序编程更加简单。
通过应用实践证明,关系模型是非常适合于客户服务器编程,远远超出预期的利益,今天它是结构化数据存储在网络和商务应用的主导技术。
NoSQL 是一项全新的数据库革命性运动,早期就有人提出,发展至2009年趋势越发高涨。NoSQL的拥护者们提倡运用非关系型的数据存储,相对于铺天盖地的关系型数据库运用,这一概念无疑是一种全新的思维的注入。

为什么使用NoSQL

今天我们可以通过第三方平台(如:Google,Facebook等)可以很容易的访问和抓取数据。用户的个人信息,社交网络,地理位置,用户生成的数据和用户操作日志已经成倍的增加。我们如果要对这些用户数据进行挖掘,那SQL数据库已经不适合这些应用了, NoSQL数据库的发展也却能很好的处理这些大的数据。

非关系型数据库举例

类型 部分代表 特点
列存储 Hbase Cassandra Hypertable 顾名思义,是按列存储数据的。最大的特点是方便存储结构化和半结构化数据,方便做数据压缩,对针对某一列或者某几列的查询有非常大的IO优势。
文档存储 MongoDB CouchDB 文档存储一般用类似json的格式存储,存储的内容是文档型的。这样也就有有机会对某些字段建立索引,实现关系数据库的某些功能。
key-value存储 Tokyo Cabinet / Tyrant Berkeley DB MemcacheDB Redis 可以通过key快速查询到其value。一般来说,存储不管value的格式,照单全收。(Redis包含了其他功能)
图存储 Neo4J FlockDB 图形关系的最佳存储。使用传统关系数据库来解决的话性能低下,而且设计使用不方便。
对象存储 db4o Versant 通过类似面向对象语言的语法操作数据库,通过对象的方式存取数据。
xml数据库 Berkeley DB XML BaseX 高效的存储XML数据,并支持XML的内部查询语法,比如XQuery,Xpath。

Redis

Redis简介

Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库,并提供多种语言的API。从2010年3月15日起,Redis的开发工作由VMware主持。从2013年5月开始,Redis的开发由Pivotal赞助。

Redis是一款速度非常快的非关系型数据库,它可以存储键(key)与5中不同类型的值(value)之间的映射(mapping)。可以将存储在内存的键值对数据持久化到硬盘,可以使用复制特性来扩展读性能,还可以使用客户端分片来扩展写性能。

Redis的数据结构

Redis可以储存键与5中不同数据结构类型的映射,这五种数据结构分别为STRING(字符串)、LIST(列表)、SET(集合)、HASH(散列)、ZSET(有序集合)。一部分Redis命令对于这5中数据结构都是通用的,如DEL、TYPE等,在入门过后,会慢慢学习Redis的数据结构深入命令与使用。

数据类型 结构存储的值 结构的读写能力
STRING 可以是字符串、整数或者浮点数 对整个字符串或者字符串的其中一部分执行操作;对整数和浮点数进行自增或者自减操作
LIST 一个链表,链表上的每个节点都包含了一给个字符串 从链表的两端推入或者弹出元素;根据偏移量对链表进行修剪;读取单个或者多个元素;根据值查找或者移除元素
SET 包含字符串的无序收集器,并且被包含的每个字符串都是独一无二,各不相同的 添加、获取、移除单个元素,检查一个元素是否存在于集合中;计算集合的并交叉;从集合里面随机获取元素
HASH 包含键值对的无序散列表 添加、获取、移除单个键值对;获取所有键值对
ZSET 字符串成员与浮点数分值之间的有序映射,元素的排列顺序由分值的大小决定 添加、获取、删除单个元素;根据分值范围或者成员来获取元素

Redis中的字符串命令

  • GET 获取存储在给定键中的值
  • SET 设置存储在给定键中的值
  • DEL 删除存储在给定键中的值 (这个命令可用于所有类型)

Redis中的列表命令

  • RPUSH 将给定值推入列表的右端
  • LRANGE 获取列表在给定范围的所有z值
  • LINDEX 获取列表在给定位置上的单个元素
  • LPOP 从列表的左端弹出一个值,并返回被弹出的值

Redis中的集合命令

  • SADD 将给顶元素添加到集合
  • SMEBERS 返回集合包含的所有元素
  • SISMEMBER 检查给定元素是否存在集合中
  • SREM 如果给定的元素存在于集合中,那么移除这个元素

Redis中的散列命令

  • HEST 在散列里面关联给定的键值对
  • HGET 获取给定散列键值对
  • HGETALL 获取散列包含的所有键值对
  • HDEL 如果给定键存在于散列里面,那么移除这个键

Redis中的有序集合命令

  • ZADD 将一个带有给定分值的成员添加到有序集合里面
  • ZRANGE 根据元素在有序排列中所处的位置,从有序集合里面获取多个位置
  • ZRANGEBYSCORE 获取有序集合在给定分值范围内的所有元素
  • ZREM 如果给定成员存在于有序集合,那么移除这个成员

Redis底层数据结构介绍

字符串

Redis 的字符串是在sds.h/sdshdr中定义,代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
struct sdshdr {

// 记录 buf 数组中已使用字节的数量
// 等于 SDS 所保存字符串的长度
int len;

// 记录 buf 数组中未使用字节的数量
int free;

// 字节数组,用于保存字符串
char buf[];

};

  • free 属性的值为 0 , 表示这个 SDS 没有分配任何未使用空间。
  • len 属性的值为 5 , 表示这个 SDS 保存了一个五字节长的字符串。
  • buf 属性是一个 char 类型的数组, 数组的前五个字节分别保存了 ‘R’ 、 ‘e’ 、 ‘d’ 、 ‘i’ 、 ‘s’ 五个字符, 而最后一个字节则保存了空字符 ‘\0’ 。

SDS 遵循 C 字符串以空字符结尾的惯例, 保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面, 并且为空字符分配额外的 1 字节空间, 以及添加空字符到字符串末尾等操作都是由 SDS 函数自动完成的, 所以这个空字符对于 SDS 的使用者来说是完全透明的。

遵循空字符结尾这一惯例的好处是, SDS 可以直接重用一部分 C 字符串函数库里面的函数。

图 2-2 展示了另一个 SDS 示例:

这个 SDS 和之前展示的 SDS 一样, 都保存了字符串值 “Redis” 。
这个 SDS 和之前展示的 SDS 的区别在于, 这个 SDS 为 buf 数组分配了五字节未使用空间, 所以它的 free 属性的值为 5 (图中使用五个空格来表示五字节的未使用空间)。

Redis SDS与C字符串的区别总结

C字符串 SDS
获取字符串长度的复杂度为 O(N) 。 获取字符串长度的复杂度为 O(1) 。
API 是不安全的,可能会造成缓冲区溢出。 API 是安全的,不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。 修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。 可以保存文本或者二进制数据。
可以使用所有 <string.h> 库中的函数。 可以使用一部分 <string.h> 库中的函数。

链表

每个链表节点使用一个 adlist.h/listNode 结构来表示:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct listNode {

// 前置节点
struct listNode *prev;

// 后置节点
struct listNode *next;

// 节点的值
void *value;

} listNode;

多个 listNode 可以通过 prev 和 next 指针组成双端链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct list {

// 表头节点
listNode *head;

// 表尾节点
listNode *tail;

// 链表所包含的节点数量
unsigned long len;

// 节点值复制函数
void *(*dup)(void *ptr);

// 节点值释放函数
void (*free)(void *ptr);

// 节点值对比函数
int (*match)(void *ptr, void *key);

} list;

list 结构为链表提供了表头指针 head 、表尾指针 tail , 以及链表长度计数器 len , 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数:

  • dup 函数用于复制链表节点所保存的值;
  • free 函数用于释放链表节点所保存的值;
  • match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。

Redis 的链表实现的特性可以总结如下:

  • 双端: 链表节点带有 prev 和 next 指针, 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
  • 无环: 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL , 对链表的访问以 NULL 为终点。
  • 带表头指针和表尾指针: 通过 list 结构的 head 指针和 tail 指针, 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
  • 带链表长度计数器: 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数, 程序获取链表中节点数量的复杂度为 O(1) 。
  • 多态: 链表节点使用 void* 指针来保存节点值, 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数, 所以链表可以用于保存各种不同类型的值。

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 结构定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictht {

// 哈希表数组
dictEntry **table;

// 哈希表大小
unsigned long size;

// 哈希表大小掩码,用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;

// 该哈希表已有节点的数量
unsigned long used;

} dictht;

table 属性是一个数组, 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针, 每个 dictEntry 结构保存着一个键值对。

size 属性记录了哈希表的大小, 也即是 table 数组的大小, 而 used 属性则记录了哈希表目前已有节点(键值对)的数量。

sizemask 属性的值总是等于 size - 1 , 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。 类似 Java 的 HashMap

dictEntry

哈希表节点使用 dictEntry 结构表示, 每个 dictEntry 结构都保存着一个键值对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dictEntry {

// 键
void *key;

// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;

// 指向下个哈希表节点,形成链表
struct dictEntry *next;

} dictEntry;

key 属性保存着键值对中的键, 而 v 属性则保存着键值对中的值, 其中键值对的值可以是一个指针, 或者是一个 uint64_t 整数, 又或者是一个 int64_t 整数。

next 属性是指向另一个哈希表节点的指针, 这个指针可以将多个哈希值相同的键值对连接在一次, 以此来解决键冲突(collision)的问题。

举个例子, 图 4-2 就展示了如何通过 next 指针, 将两个索引值相同的键 k1 和 k0 连接在一起。

字典

Redis 中的字典由 dict.h/dict 结构表示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef struct dict {

// 类型特定函数
dictType *type;

// 私有数据
void *privdata;

// 哈希表
dictht ht[2];

// rehash 索引
// 当 rehash 不在进行时,值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type 属性和 privdata 属性是针对不同类型的键值对, 为创建多态字典而设置的:

type 属性是一个指向 dictType 结构的指针, 每个 dictType 结构保存了一簇用于操作特定类型键值对的函数, Redis 会为用途不同的字典设置不同的类型特定函数。
而 privdata 属性则保存了需要传给那些类型特定函数的可选参数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct dictType {

// 计算哈希值的函数
unsigned int (*hashFunction)(const void *key);

// 复制键的函数
void *(*keyDup)(void *privdata, const void *key);

// 复制值的函数
void *(*valDup)(void *privdata, const void *obj);

// 对比键的函数
int (*keyCompare)(void *privdata, const void *key1, const void *key2);

// 销毁键的函数
void (*keyDestructor)(void *privdata, void *key);

// 销毁值的函数
void (*valDestructor)(void *privdata, void *obj);

} dictType;

ht 属性是一个包含两个项的数组, 数组中的每个项都是一个 dictht 哈希表, 一般情况下, 字典只使用 ht[0] 哈希表, ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。

除了 ht[1] 之外, 另一个和 rehash 有关的属性就是 rehashidx : 它记录了 rehash 目前的进度, 如果目前没有在进行 rehash , 那么它的值为 -1 。

图 4-3 展示了一个普通状态下(没有进行 rehash)的字典:

在经过 hash 后的键值对会进行 hash & sizemask 运算计算存储的下标,与 Java 的 HashMap 是一样的,在哈希冲突上采用的是拉链法,也和 HashMap 一样。

渐进式 rehash

扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面, 但是, 这个 rehash 动作并不是一次性、集中式地完成的, 而是分多次、渐进式地完成的。

这样做的原因在于, 如果 ht[0] 里只保存着四个键值对, 那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1] ; 但是, 如果哈希表里保存的键值对数量不是四个, 而是四百万、四千万甚至四亿个键值对, 那么要一次性将这些键值对全部 rehash 到 ht[1] 的话, 庞大的计算量可能会导致服务器在一段时间内停止服务。

因此, 为了避免 rehash 对服务器性能造成影响, 服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1] , 而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1] 。

以下是哈希表渐进式 rehash 的详细步骤:

  1. 为 ht[1] 分配空间, 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx , 并将它的值设置为 0 , 表示 rehash 工作正式开始。
  3. 在 rehash 进行期间, 每次对字典执行添加、删除、查找或者更新操作时, 程序除了执行指定的操作以外, 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] , 当 rehash 工作完成之后, 程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行, 最终在某个时间点上, ht[0] 的所有键值对都会被 rehash 至 ht[1] , 这时程序将 rehashidx 属性的值设为 -1 , 表示 rehash 操作已完成。
    渐进式 rehash 的好处在于它采取分而治之的方式, 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上, 从而避免了集中式 rehash 而带来的庞大计算量。

整数集合

整数集合(intset)是 Redis 用于保存整数值的集合抽象数据结构, 它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值, 并且保证集合中不会出现重复元素。

每个 intset.h/intset 结构表示一个整数集合:

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct intset {

// 编码方式
uint32_t encoding;

// 集合包含的元素数量
uint32_t length;

// 保存元素的数组
int8_t contents[];

} intset;

contents 数组是整数集合的底层实现: 整数集合的每个元素都是 contents 数组的一个数组项(item), 各个项在数组中按值的大小从小到大有序地排列, 并且数组中不包含任何重复项。

length 属性记录了整数集合包含的元素数量, 也即是 contents 数组的长度。

虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组, 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值:

  • 如果 encoding 属性的值为 INTSET_ENC_INT16 , 那么 contents 就是一个 int16_t 类型的数组, 数组里的每个项都是一个 int16_t 类型的整数值 (最小值为 -32,768 ,最大值为 32,767 )。
  • 如果 encoding 属性的值为 INTSET_ENC_INT32 , 那么 contents 就是一个 int32_t 类型的数组, 数组里的每个项都是一个 int32_t 类型的整数值 (最小值为 -2,147,483,648 ,最大值为 2,147,483,647 )。
  • 如果 encoding 属性的值为 INTSET_ENC_INT64 , 那么 contents 就是一个 int64_t 类型的数组, 数组里的每个项都是一个 int64_t 类型的整数值 (最小值为 -9,223,372,036,854,775,808 ,最大值为 9,223,372,036,854,775,807 )。

图 6-1 展示了一个整数集合示例:

  • encoding 属性的值为 INTSET_ENC_INT16 , 表示整数集合的底层实现为 int16_t 类型的数组, 而集合保存的都是 int16_t 类型的整数值。
  • length 属性的值为 5 , 表示整数集合包含五个元素。
  • contents 数组按从小到大的顺序保存着集合中的五个元素。
  • 因为每个集合元素都是 int16_t 类型的整数值, 所以 contents 数组的大小等于 sizeof(int16_t) 5 = 16 5 = 80 位。

图 6-2 展示了另一个整数集合示例:

  • encoding 属性的值为 INTSET_ENC_INT64 , 表示整数集合的底层实现为 int64_t 类型的数组, 而数组中保存的都是 int64_t 类型的整数值。
  • length 属性的值为 4 , 表示整数集合包含四个元素。
  • contents 数组按从小到大的顺序保存着集合中的四个元素。
  • 因为每个集合元素都是 int64_t 类型的整数值, 所以 contents 数组的大小为 sizeof(int64_t) 4 = 64 4 = 256 位。

虽然 contents 数组保存的四个整数值中, 只有 -2675256175807981027 是真正需要用 int64_t 类型来保存的, 而其他的 1 、 3 、 5 三个值都可以用 int16_t 类型来保存, 不过根据整数集合的升级规则, 当向一个底层为 int16_t 数组的整数集合添加一个 int64_t 类型的整数值时, 整数集合已有的所有元素都会被转换成 int64_t 类型, 所以 contents 数组保存的四个整数值都是 int64_t 类型的, 不仅仅是 -2675256175807981027 。

总结

今天主要对非关系型数据库(NoSQL)进行初步认识,以及以键值对类型的Redis的初步认识以及Redis五大数据结构的入门,今后会继续对Java中Redis的操作Jedis、Redis的深入操作,持久化等更多知识进行学习和总结。

参考资料

  • Redis In Action
  • Redis 设计与实现