黄雷同学问的B-tree实现terms和在文档中位置关系的问题能陈述一下吗？

[Hongfei Yan]

便于实现过的同学帮忙解答一下。

谢谢

-闫宏飞

[黄雷]

问题描述：

在第四次作业中，我对倒排表（只包含docId）和位置表使用B+树，

在倒排表上，key = termId, value = 倒排文件的偏移指针 （倒排表就对应着两个文件：对应的B+树文件和倒排文件）；

在位置表上，key = termId, value = 位置文件的偏移指针（位置表就对应着两个文件：对应的B+树文件和位置文件）；

但是，这样每次读取位置表时，都需要把一个term下的所有docId对应的位置表都读出来，耗时比较大，特别是在查询经常出现的term时延迟明显。

之前助教评讲作业时，在ppt中介绍到

“用在位置链表上，key = 文档id，value=位置文件的指针”

如果对于位置链表只生成两个文件（对应的B+树文件和位置文件），那么键值key就会冲突，因为不同term的倒排文件可能有相同的docId；

如果对于每个term的位置链表都生成两个文件，那文件个数太多操作也不太方便。

希望大家讨论下解决方案，给出意见，帮忙解决作业中遇到的困惑。

Hongfei Yan於 2014年4月30日星期三UTC+8下午8時32分05秒寫道：

便于实现过的同学帮忙解答一下。

谢谢

-闫宏飞

[Han Jiang]

黄雷你好，我是上回讲B+树的助教。

我们倒排表的本质其实就是一个map<long long, map<long long, vector<long long> > > 的结构吧。

其中，第一层map表示从term_id到文档集的映射，第二层map表示doc_id到位置列表的映射。

所以，我先前讲ppt时的想法是，既然B+树已经可以抽象为一个map了，那么，这两层的映射关系就可以用B+树实现了。所以，我的想法是针对每一个文档都构造一棵B+树哈。

关于"每个term的位置链表都生成两个文件"这一点，我有疑问，是怎样“操作不方便”呢？

--
You received this message because you are subscribed to the Google Groups "cs410pku" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cs410pku+u...@googlegroups.com.
To post to this group, send email to cs41...@googlegroups.com.
Visit this group at http://groups.google.com/group/cs410pku.
For more options, visit https://groups.google.com/d/optout.

--
Han Jiang

Team of Search Engine and Web Mining,
School of Electronic Engineering and Computer Science,
Peking University, China

[黄雷]

助教的在ppt中给出的方法是：<termId, <docId, positionList>>，两层map，其中positionList是一个文档的位置链表

在第一层map，<termId, 倒排文件偏移指针>，建立B+树，最后得到两个文件，B+树文件和倒排文件；

在第二层map，<docId, 位置文件偏移指针>，建立B+树，即每个term对应一个位置链表的B+树，这样每个term的位置链表就会得到两个文件，B+树文件和位置链表文件；对于N个term，就会有2*N个文件，个人只是感觉文件有点多而已。（不知是否理解了助教的方法）

所以就把第二层map改成了<termId, 位置文件偏移指针>，建立B+树，这样每次就必须读入一个term对应的所有文档的位置信息，速度有点慢。

估计考虑到速度，还是采用助教建议的方法更好。

Han Jiang於 2014年5月5日星期一UTC+8上午9時54分43秒寫道：

[Han Jiang]

嗯，如果第二层用map实现的话，确实会出现文件过多的情况，你可以考虑下面两种实现：
1.  在设计B+树时，所有B+树的结点都共享一个公共的文件中(比如，某个B+树的根结点id是9，另一个B+树根结点id是100，这表示它们分别在文件的第9个块和第100个块中。
2.  对于第二层映射直接抛弃B+树的实现。因为我们并不要求*过于*节省内存，而对于一个term加载它所有的doc id，以及对于一个doc id，加载它所有的position list是可以允许的，这时，除了词典用B+树来设计外，下层的两个map可以考虑直接用链表来存的。

希望有所帮助！