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