问题描述

一张图由若干节点和连接节点的边组成。本文考虑如何利用Redis保存所有节点和边的信息，并且支持给定任意节点，查询出与其联通的所有节点。所谓联通，指的是两个节点之间一定有一条若干条边组成的路径。

如上需求可以使用专门的图数据库(如neo4j)进行实现。但实际上，只要进行恰当的设计，并结合一些设定，使用Redis也可以实现如上需求。

节点信息存储方法

首先，我们需要用到Redis的散列类型来存储节点的信息。key为节点的唯一标识id(以下称为节点id)，value为散列表，保存节点的各种信息。

如下是一个简单的例子，假设有三个节点，id为1，2，3，4，5。代表五个人，每个人都有姓名，年龄，职业三个属性，则每个人的数据的存储方式如下（以id为1的人为例）：

hset person:1 name mike
hset person:1 age 23
hset person:1 profession engineer

节点联通关系存储方法

使用Redis的集合类型表示节点之间的联通关系。注意，这里抛弃掉了边的信息，仅保留联通关系。即抛弃掉了两个节点联通的具体路径。

假设存在如下的五个人有如下的朋友（联通）关系：

1 -- 2, 2 -- 3, 4 -- 5, 5 -- 2

我们希望通过特定的算法，当这四个联通关系依次入库后，redis数据库中有如下的存储结构：

friend:1 [1, 2, 3, 4, 5]
friend:2 [1]
friend:3 [1]
friend:4 [1]
friend:5 [1]

从上面四个联通关系可以看出，实际上1，2，3，4，5是彼此联通的，那么就构成了一个联通图。每一个联通图，需要按照一定原则选举出一个代表节点。该节点的关系键保存完成的联通成员信息。而其余成员节点的关系键均指向该代表性节点。以上面的例子为例，节点的选举原则是选取联通图中编号最小的节点。则1为代表性节点，则friend:1中保存了完整的联通成员信息。节点2-5则仅保存与1联通。这样保存的目的是防止数据的冗余存储。联通图假设有n个成员，则需要的存储空间为2*n-1。

为了达到上面的存储效果，需要在入库时对关系键进行一些调整操作，具体步骤如下：

步骤1 获取关联关系的左右两个节点，检查是否存在节点的关系键，若没有则创建关系键并将自身加入关系集合

sadd friend:1 1 
sadd friend:2 2 

步骤2 针对每个节点的关系键，获取其关联的所有节点中id最小的节点（注意，若使用有序集合，最小节点将更方便求解，此处以普通集合为例）。如下为伪代码，混合了redis命令和java的赋值命令

set1 =  smems friend:1 //将friend:1中的集合保存在set1
set2 =  smems friend:2
std1 = min(set1)//取set1中最小的元素
std2 = min(set2)

步骤3 找出std1和std2的较小值和较大值

stdMin = std1>std2? std2:std1
stdMax = std1>std2? std1:std2

步骤4 若stdMin==stdMax则无需进行任何操作，否则将stdMax中的所有元素都加入到stdMin中，且stdMax中的元素对应的关系键全部设置成stdMin

members = smems friend:stdMax
//stdMax中的元素对应的关系键全部设置成stdMin
for(String member:members){
    del friend:member
    sadd friend:member stdMin
}
//将friend:stdMin和friend:stdMax中的元素合并，并将结果放入stdMin
smerge friend:stdMin friend:stdMin friend:stdMax

每一个关联关系的入库都需要如上四步。如果存在多线程入库的情况，需要将其形成一个事务处理。下面以1 -- 2, 2 -- 3, 4 -- 5, 5 -- 2的入库顺序逐步进行推演：

入库1 -- 2

步骤1后为：

friend:1 [1]
friend:2 [2]

步骤2: 得到1中元素最小为1，2中元素最小为2
步骤3: stdMin=1，stdMax=2
步骤4：将2中元素归到1，并设置2中元素的关系键内容为1

friend:1 [1,2]
friend:2 1

入库2 -- 3

步骤1后为（创建了3的关系键）：

friend:1 [1,2]
friend:2 [1]
friend:3 [3]

步骤2: 得到2中元素最小为1，3中元素最小为3
步骤3: stdMin=1，stdMax=3
步骤4：将3中元素归到1，并设置3中元素的关系键内容为1

friend:1 [1,2,3]
friend:2 [1]
friend:3 [1]

入库4 -- 5

步骤1后为（创建了4和5的关系键）：

friend:1 [1,2,3]
friend:2 [1]
friend:3 [1]
friend:4 [4]
friend:5 [5]

步骤2: 得到4中元素最小为4，5中元素最小为5
步骤3: stdMin=4，stdMax=5
步骤4：将4中元素归到5，并设置4中元素的关系键内容为5

friend:1 [1,2,3]
friend:2 [1]
friend:3 [1]
friend:4 [4,5]
friend:5 [4]

入库5 -- 2

步骤1后为(无变化）：

friend:1 [1,2,3]
friend:2 [1]
friend:3 [1]
friend:4 [4,5]
friend:5 [4]

步骤2: 得到5中元素最小为4，2中元素最小为1
步骤3: stdMin=1，stdMax=4
步骤4：将4中元素归到1，并设置4中元素的关系键内容为1

friend:1 [1,2,3,4,5]
friend:2 [1]
friend:3 [1]
friend:4 [1]
friend:5 [1]

联通关系的获取方法

基于如上构造的redis数据存储，可以方便的给定任意一个节点，找出与其联通的所有节点。仅需要如下两个步骤

1. 获取该节点的关系键，若不存在则返回空值
2. 若关系键存在，则获取其值。若值中包含键id本身（如friend:1对应的集合中包含1），则直接返回值。否则返回值中id对应的关系键中的内容（如friend:4的集合中没有4，仅有1，则返回friend:1对应的集合）。