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