問題描述
一張圖由若干節(jié)點(diǎn)和連接節(jié)點(diǎn)的邊組成。本文考慮如何利用Redis保存所有節(jié)點(diǎn)和邊的信息，并且支持給定任意節(jié)點(diǎn)晴玖，查詢出與其聯(lián)通的所有節(jié)點(diǎn)晶默。所謂聯(lián)通谨娜，指的是兩個節(jié)點(diǎn)之間一定有一條若干條邊組成的路徑。
如上需求可以使用專門的圖數(shù)據(jù)庫(如neo4j)進(jìn)行實(shí)現(xiàn)磺陡。但實(shí)際上趴梢，只要進(jìn)行恰當(dāng)?shù)脑O(shè)計(jì)，并結(jié)合一些設(shè)定币他，使用Redis也可以實(shí)現(xiàn)如上需求坞靶。
節(jié)點(diǎn)信息存儲方法
首先，我們需要用到Redis的散列類型來存儲節(jié)點(diǎn)的信息圆丹。key為節(jié)點(diǎn)的唯一標(biāo)識id(以下稱為節(jié)點(diǎn)id)滩愁，value為散列表，保存節(jié)點(diǎn)的各種信息辫封。
如下是一個簡單的例子硝枉，假設(shè)有三個節(jié)點(diǎn)，id為1倦微，2妻味，3，4欣福，5责球。代表五個人，每個人都有姓名，年齡雏逾，職業(yè)三個屬性嘉裤，則每個人的數(shù)據(jù)的存儲方式如下（以id為1的人為例）：
hset person:1 name mike
hset person:1 age 23
hset person:1 profession engineer
節(jié)點(diǎn)聯(lián)通關(guān)系存儲方法
使用Redis的集合類型表示節(jié)點(diǎn)之間的聯(lián)通關(guān)系。注意栖博，這里拋棄掉了邊的信息屑宠，僅保留聯(lián)通關(guān)系。即拋棄掉了兩個節(jié)點(diǎn)聯(lián)通的具體路徑仇让。
假設(shè)存在如下的五個人有如下的朋友（聯(lián)通）關(guān)系：
1 -- 2, 2 -- 3, 4 -- 5, 5 -- 2
我們希望通過特定的算法典奉，當(dāng)這四個聯(lián)通關(guān)系依次入庫后，redis數(shù)據(jù)庫中有如下的存儲結(jié)構(gòu)：
friend:1 [1, 2, 3, 4, 5]
friend:2 [1]
friend:3 [1]
friend:4 [1]
friend:5 [1]
從上面四個聯(lián)通關(guān)系可以看出丧叽，實(shí)際上1卫玖，2，3踊淳，4假瞬，5是彼此聯(lián)通的，那么就構(gòu)成了一個聯(lián)通圖嚣崭。每一個聯(lián)通圖笨触，需要按照一定原則選舉出一個代表節(jié)點(diǎn)。該節(jié)點(diǎn)的關(guān)系鍵保存完成的聯(lián)通成員信息雹舀。而其余成員節(jié)點(diǎn)的關(guān)系鍵均指向該代表性節(jié)點(diǎn)芦劣。以上面的例子為例，節(jié)點(diǎn)的選舉原則是選取聯(lián)通圖中編號最小的節(jié)點(diǎn)说榆。則1為代表性節(jié)點(diǎn)虚吟，則friend:1中保存了完整的聯(lián)通成員信息。節(jié)點(diǎn)2-5則僅保存與1聯(lián)通签财。這樣保存的目的是防止數(shù)據(jù)的冗余存儲串慰。聯(lián)通圖假設(shè)有n個成員，則需要的存儲空間為2*n-1唱蒸。
為了達(dá)到上面的存儲效果邦鲫，需要在入庫時對關(guān)系鍵進(jìn)行一些調(diào)整操作，具體步驟如下：
步驟1 獲取關(guān)聯(lián)關(guān)系的左右兩個節(jié)點(diǎn)神汹，檢查是否存在節(jié)點(diǎn)的關(guān)系鍵庆捺，若沒有則創(chuàng)建關(guān)系鍵并將自身加入關(guān)系集合
sadd friend:1 1
sadd friend:2 2
步驟2 針對每個節(jié)點(diǎn)的關(guān)系鍵，獲取其關(guān)聯(lián)的所有節(jié)點(diǎn)中id最小的節(jié)點(diǎn)（注意屁魏，若使用有序集合滔以，最小節(jié)點(diǎn)將更方便求解，此處以普通集合為例）氓拼。如下為偽代碼你画，混合了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則無需進(jìn)行任何操作抵碟，否則將stdMax中的所有元素都加入到stdMin中，且stdMax中的元素對應(yīng)的關(guān)系鍵全部設(shè)置成stdMin
members = smems friend:stdMax
//stdMax中的元素對應(yīng)的關(guān)系鍵全部設(shè)置成stdMin
for(String member:members){
del friend:member
sadd friend:member stdMin
}
//將friend:stdMin和friend:stdMax中的元素合并坏匪，并將結(jié)果放入stdMin
smerge friend:stdMin friend:stdMin friend:stdMax
每一個關(guān)聯(lián)關(guān)系的入庫都需要如上四步拟逮。如果存在多線程入庫的情況，需要將其形成一個事務(wù)處理适滓。下面以1 -- 2, 2 -- 3, 4 -- 5, 5 -- 2的入庫順序逐步進(jìn)行推演：
入庫1 -- 2
步驟1后為：
friend:1 [1]
friend:2 [2]
步驟2: 得到1中元素最小為1唱歧，2中元素最小為2
步驟3: stdMin=1，stdMax=2
步驟4：將2中元素歸到1粒竖，并設(shè)置2中元素的關(guān)系鍵內(nèi)容為1
friend:1 [1,2]
friend:2 1
入庫2 -- 3
步驟1后為（創(chuàng)建了3的關(guān)系鍵）：
friend:1 [1,2]
friend:2 [1]
friend:3 [3]
步驟2: 得到2中元素最小為1，3中元素最小為3
步驟3: stdMin=1几于，stdMax=3
步驟4：將3中元素歸到1蕊苗，并設(shè)置3中元素的關(guān)系鍵內(nèi)容為1
friend:1 [1,2,3]
friend:2 [1]
friend:3 [1]
入庫4 -- 5
步驟1后為（創(chuàng)建了4和5的關(guān)系鍵）：
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朽砰，并設(shè)置4中元素的關(guān)系鍵內(nèi)容為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瞧柔，并設(shè)置4中元素的關(guān)系鍵內(nèi)容為1
friend:1 [1,2,3,4,5]
friend:2 [1]
friend:3 [1]
friend:4 [1]
friend:5 [1]
聯(lián)通關(guān)系的獲取方法
基于如上構(gòu)造的redis數(shù)據(jù)存儲，可以方便的給定任意一個節(jié)點(diǎn)睦裳，找出與其聯(lián)通的所有節(jié)點(diǎn)造锅。僅需要如下兩個步驟
- 獲取該節(jié)點(diǎn)的關(guān)系鍵，若不存在則返回空值
- 若關(guān)系鍵存在廉邑，則獲取其值哥蔚。若值中包含鍵id本身（如friend:1對應(yīng)的集合中包含1），則直接返回值蛛蒙。否則返回值中id對應(yīng)的關(guān)系鍵中的內(nèi)容（如friend:4的集合中沒有4糙箍，僅有1，則返回friend:1對應(yīng)的集合）牵祟。
