摘要：簡(jiǎn)單地說(shuō)，倒排索引就是把與對(duì)調(diào)之后的索引，構(gòu)建倒排索引的目的是提升搜索性能。本文將介紹中兩種構(gòu)建倒排索引的方法與。
摘要: 為MongoDB中的數(shù)據(jù)構(gòu)建倒排索引(Inverted Index)，然后緩存到內(nèi)存中，可以大幅提升搜索性能。本文將通過(guò)為電影數(shù)據(jù)構(gòu)建演員索引，介紹兩種構(gòu)建倒排索引的方法：MapReduce和Aggregation Pipeline。
GitHub地址:
作者: KiwenLau
日期: 2016-09-11
一. 倒排索引
倒排索引(Inverted Index)，也稱(chēng)為反向索引，維基百科的定義是這樣的:
是一種索引方法，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。
這個(gè)定義比較學(xué)術(shù)，也就是比較反人類(lèi)，忽略...
倒排索引是搜索引擎中的核心數(shù)據(jù)結(jié)構(gòu)。搜索引擎的爬蟲(chóng)獲取的網(wǎng)頁(yè)數(shù)據(jù)可以視為鍵值對(duì)，其中，Key是網(wǎng)頁(yè)地址(url)，而Value是網(wǎng)頁(yè)內(nèi)容。網(wǎng)頁(yè)的內(nèi)容是由很多關(guān)鍵詞(word)組成的，可以視為關(guān)鍵詞數(shù)組。因此，爬蟲(chóng)獲取的網(wǎng)頁(yè)數(shù)據(jù)可以這樣表示:
但是，用戶(hù)是通過(guò)關(guān)鍵詞進(jìn)行搜索的，直接使用原始數(shù)據(jù)進(jìn)行查詢(xún)的話則需要遍歷所有鍵值對(duì)中的關(guān)鍵詞數(shù)組，效率是非常低的。
因此，用于搜索的數(shù)據(jù)結(jié)構(gòu)應(yīng)該以關(guān)鍵詞(word)為Key，以網(wǎng)頁(yè)地址(url)為Value:
這樣的話，查詢(xún)關(guān)鍵詞word2，立即能夠獲取結(jié)果: [ur1, url2, url3]。
簡(jiǎn)單地說(shuō)，倒排索引就是把Key與Value對(duì)調(diào)之后的索引，構(gòu)建倒排索引的目的是提升搜索性能。
二. 測(cè)試數(shù)據(jù)
MongoDB是文檔型數(shù)據(jù)庫(kù)，其數(shù)據(jù)有三個(gè)層級(jí): 數(shù)據(jù)庫(kù)(database)，集合(collection)和文檔(document)，分別對(duì)應(yīng)關(guān)系型數(shù)據(jù)庫(kù)中的三個(gè)層級(jí)的: 數(shù)據(jù)庫(kù)(database), 表(table)，行(row)。MongDB中每個(gè)的文檔是一個(gè)JSON文件，例如，本文使用的movie集合中的一個(gè)文檔如下所示:
{
"_id" : ObjectId("57d02d60b128567fc130287d"),
"movie" : "Pride & Prejudice",
"starList" : [
"Keira Knightley",
"Matthew Macfadyen"
],
"__v" : 0
}
該文檔一共有4個(gè)屬性:
_id: 文檔ID，由MongoDB自動(dòng)生成。
__v: 文檔版本，由MongoDB的NodeJS接口Mongoose自動(dòng)生成。
movie: 電影名稱(chēng)。
starList: 演員列表。
可知，這個(gè)文檔表示電影《傲慢與偏見(jiàn)》，由女神凱拉·奈特莉主演。
忽略_id與__v，movie集合的數(shù)據(jù)如下:
{
"movie": "Pride & Prejudice",
"starList": ["Keira Knightley", "Matthew Macfadyen"]
},
{
"movie": "Begin Again",
"starList": ["Keira Knightley", "Mark Ruffalo"]
},
{
"movie": "The Imitation Game",
"starList": ["Keira Knightley", "Benedict Cumberbatch"]
}
其中，Key為電影名稱(chēng)(movie)，而Value為演員列表(starList)。
這時(shí)查詢(xún)Keira Knightley所主演的電影的NodeJS代碼如下:
Movie.find(
{
starList: "Keira Knightley"
},
{
_id: 0,
movie: 1
}, function(err, results)
{
if (err)
{
console.log(err);
process.exit(1);
}
console.log("search movie success:
");
console.log(JSON.stringify(results, null, 4));
process.exit(0);
});
注：本文所有代碼使用了MongoDB的NodeJS接口Mongoose，它與MongoDB Shell的接口基本一致。
代碼并不復(fù)雜，但是數(shù)據(jù)量大時(shí)查詢(xún)性能會(huì)很差，因?yàn)檫@個(gè)查詢(xún)需要:
遍歷整個(gè)movie集合的所有文檔
遍歷每個(gè)文檔的startList數(shù)組
構(gòu)建倒排索引可以有效地提升搜索性能。本文將介紹MongoDB中兩種構(gòu)建倒排索引的方法：MapReduce與Aggregation Pipeline。
三 MapReduce
MapReduce是由谷歌提出的編程模型，適用于多種大數(shù)據(jù)處理場(chǎng)景，在搜索引擎中，MapReduce可以用于構(gòu)建網(wǎng)頁(yè)數(shù)據(jù)的倒排索引，也可以用于編寫(xiě)網(wǎng)頁(yè)排序算法PageRank(由谷歌創(chuàng)始人佩奇和布林提出)。
MapReduce的輸入數(shù)據(jù)與輸出數(shù)據(jù)均為鍵值對(duì)。MapReduce分為兩個(gè)函數(shù): Map與Reduce。
Map函數(shù)將輸入鍵值對(duì)進(jìn)行變換，輸出中間鍵值對(duì)。
MapReduce框架會(huì)自動(dòng)對(duì)中間鍵值對(duì)進(jìn)行分組，Key相同的鍵值對(duì)會(huì)被合并為一個(gè)鍵值對(duì)。
Reduce函數(shù)對(duì)的Value進(jìn)行合并，生成結(jié)果鍵值對(duì)。
使用MapReduce構(gòu)建倒排索引的NodeJS代碼如下:
var option = {};
option.map = function()
{
var movie = this.movie;
this.starList.forEach(function(star)
{
emit(star,
{
movieList: [movie]
});
});
};
option.reduce = function(key, values)
{
var movieList = [];
values.forEach(function(value)
{
movieList.push(value.movieList[0]);
});
return {
movieList: movieList
};
};
Movie.mapReduce(option, function(err, results)
{
if (err)
{
console.log(err);
process.exit(1);
}
console.log("create inverted index success:
");
console.log(JSON.stringify(results, null, 4));
process.exit(0);
});
代碼解釋:
Map函數(shù)的輸入數(shù)據(jù)是Movie集合中的各個(gè)文檔，在代碼中用this表示。文檔的movie與starList屬性構(gòu)成鍵值對(duì)。Map函數(shù)遍歷starList，為每個(gè)start生成鍵值對(duì)。這時(shí)Key與Value進(jìn)行了對(duì)調(diào)，且starList被拆分了，movieList僅包含單個(gè)movie。
MongoDB的MapReduce執(zhí)行框架對(duì)成鍵值對(duì)進(jìn)行分組，star相同的鍵值對(duì)會(huì)被合并為一個(gè)鍵值對(duì)。這一步是自動(dòng)進(jìn)行的，因此在代碼中并沒(méi)有體現(xiàn)。
Reduce函數(shù)的輸入數(shù)據(jù)是鍵值對(duì)，在代碼中，star即為key，而list(movieList)即為values，兩者為Reduce函數(shù)的參數(shù)。Reduce函數(shù)合并list(movieList)，從而得到鍵值對(duì)，最終，movieList中將包含該star的所有movie。
在代碼中，Map函數(shù)與Reduce返回的鍵值對(duì)中的Value是一個(gè)對(duì)象{ movieList: movieList }，而不是數(shù)組movieList，因此代碼和結(jié)果都顯得比較奇怪。MongoDB的MapReduce框架不支持Reduce函數(shù)返回?cái)?shù)組，因此只能將movieList放在對(duì)象里面返回。
輸出結(jié)果:
[
{
"_id": "Benedict Cumberbatch",
"value": {
"movieList": [
"The Imitation Game"
]
}
},
{
"_id": "Keira Knightley",
"value": {
"movieList": [
"Pride & Prejudice",
"Begin Again",
"The Imitation Game"
]
}
},
{
"_id": "Mark Ruffalo",
"value": {
"movieList": [
"Begin Again"
]
}
},
{
"_id": "Matthew Macfadyen",
"value": {
"movieList": [
"Pride & Prejudice"
]
}
}
]
四. Aggregation Pipeline
Aggregation Pipeline，中文稱(chēng)作聚合管道，用于匯總MongoDB中多個(gè)文檔中的數(shù)據(jù)，也可以用于構(gòu)建倒排索引。
Aggregation Pipeline進(jìn)行各種聚合操作，并且可以將多個(gè)聚合操作組合使用，類(lèi)似于Linux中的管道操作，前一個(gè)操作的輸出是下一個(gè)操作的輸入。
使用Aggregation Pipeline構(gòu)建倒排索引的NodeJS代碼如下:
Movie.aggregate([
{
"$unwind": "$starList"
},
{
"$group":
{
"_id": "$starList",
"movieList":
{
"$push": "$movie"
}
}
},
{
"$project":
{
"_id": 0,
"star": "$_id",
"movieList": 1
}
}], function(err, results)
{
if (err)
{
console.log(err);
process.exit(1);
}
console.log("create inverted index success:
");
console.log(JSON.stringify(results, null, 4));
process.exit(0);
});
代碼解釋:
$unwind: 將starList拆分，輸出結(jié)果(忽略_id與__v)為:
[
{
"movie": "Pride & Prejudice",
"starList": "Keira Knightley"
},
{
"movie": "Pride & Prejudice",
"starList": "Matthew Macfadyen"
},
{
"movie": "Begin Again",
"starList": "Keira Knightley"
},
{
"movie": "Begin Again",
"starList": "Mark Ruffalo"
},
{
"movie": "The Imitation Game",
"starList": "Keira Knightley"
},
{
"movie": "The Imitation Game",
"starList": "Benedict Cumberbatch"
}
]
$group: 根據(jù)文檔的starList屬性進(jìn)行分組，然后將分組文檔的movie屬性合并為movieList，輸出結(jié)果為:
[
{
"_id": "Benedict Cumberbatch",
"movieList": [
"The Imitation Game"
]
},
{
"_id": "Matthew Macfadyen",
"movieList": [
"Pride & Prejudice"
]
},
{
"_id": "Mark Ruffalo",
"movieList": [
"Begin Again"
]
},
{
"_id": "Keira Knightley",
"movieList": [
"Pride & Prejudice",
"Begin Again",
"The Imitation Game"
]
}
]
