至此为止,我们已经逐渐了解了倒排索引的逻辑结构。下面,就让我们再来了解一下倒排索引的具体实现吧。 实现词典 在实现词典时,为了能够快速地获取到对应着单词的倒排列表,通常都会使用哈希表、树等数据结构。例如,常用的树形数据结构有保存着各个单词顺序关系的二叉查找树(Binary Search Tree)和字典树(Trie)等。 用二叉查找树实现词典 使用二叉查找树实现词典时,要先将数据对(的列表)按照单词的词典顺序排列,然后存储到存储器中。数据对是由单词和对应着该单词的倒排列表的引用信息构成的。例如,若用内存上的二叉查找树实现之前例子中的词典,就会得到如图1-3 所示的树形结构。树中的各个结点是通过地址引用(指针)连接起来的。 图1-3 在内存上实现词典(使用二叉查找树) 同样地,在二级存储上实现词典时,也要先将数据对按照单词的词典顺序排列,然后一个接一个地存储到存储器上。但是,如果只是单纯地一个接一个地存储,就无法知道各数据对应该在哪里结束了,因此在此之上还要维护一个列表, 用于存储从开头算起每个数据对的偏移量。对应的数据结构如图1-4 所示。在进行检索时,可以对该偏移量的列表进行二分查找。 图1-4 在二级存储器上实现词典(使用二叉查找树) 如果词典能够完整地加载到内存,那么所形成的二叉树的搜索效率将会非常高。特别是当二叉树处于平衡状态时,平均进行log2N 次查找就能找到单词。 但是,如果词典无法完整地加载到内存,而必须存储到二级存储器上时,二叉树就未必是高效的数据结构了。HDD 或SSD 等二级存储器一般被称作“块设备”,由于它们是以块为单位进行输入输出的A,所以即使只是读取块中1 个字节的数据,也不得不对整个块进行输入输出操作。例如,假设我们用二叉查找树实现了含有100 万个单词的词典,那么进行二分查找的话,平均需要20 次查找,因此在最坏的情况下就需要加载20 个块。也就是说,假设二级存储的加载性能为5ms/ 块,那么在1 次检索中,仅花费在二级存储输入输出上的时间就高达100ms。 因此,当要存储大型词典时,往往要使用适合块设备的B+ 树等树形数据结构。 ---————— A HDD 的最小输入输出单位是512 字节的扇区。文件系统通常以页为单位来管理存储空间(空间大小是设备块大小的常数倍),并以页为单位进行输入输出。Linux 通常以4KB 为一页。 ———————— 用B+树实现词典 B+ 树是一种平衡的多叉树,属于从B 树派生出来的树形结构。在B+ 树中,所有的记录都存储在树中的叶结点(Leaf Node)上,内部结点(Internal Node)上只 以关键字的顺序存储关键字A。B+ 树的示意图如图1-5 所示。 图1-5 在二级存储器上实现词典(使用B+ 树) B+ 树通常以文件系统中页尺寸的常数倍为单位管理各结点,而由这样的结点来构成树,则有助于减少检索时对二级存储的输入输出次数(详细内容请参考书后的参考文献1)。 下面就让我们用B+ 树来实现之前的包含了100 万个单词的词典吧。假设有以下设定。 块大小:4KB 页大小:4KB 单词的平均大小:10字节 页内偏移量的大小:2字节B 指向下一级结点的指针的大小:4字节 基于这种假设,可以算出每个单词将占用页中16 个字节的空间,因此每页中可以存放大约250 个关键词(单词)C。由于页中的每个单词都持有一个指向下级结点 的指针,下级结点中存储的是按照词典顺序排在该单词之前(后)的单词集合,所以可以推算出要存储100 万个单词只需要3 层结点就足够了(100 万< 250× 250×250 =约1500 万)。也就是说,只要从二级存储中读取3 个结点,就可以检索到任意的单词了。假设二级存储的加载性能还是5ms/ 块,那么花在检索上的输入输出时间就是15ms,这与花费在二叉查找树检索上的100ms 的输入输出时间形成了鲜明的对比。 ----———————— A 由于在数据库管理系统中B+ 树用得非常普遍,所以也经常可以遇到虽然说的是B 树,但实际上指的是B+ 树的情景。 B 由于单词的长度不是固定的,所以为了指示出每个单词在页中的保存位置,通常还要维护一个偏移量的数组。 C 为了估算输入输出的次数,这里仅进行了非常粗略地计算。实际上每一页中还包含着用于管理该页信息的头部,而且如果一页中有N 个单词的话,就还会有N + 1 个指针。 ———————————— 实现倒排文件 在实现倒排文件时,往往会假设所有倒排列表都会变得很长,因此一般都会将倒排列表存储到二级存储的连续区域中A。由此就可以通过二级存储的顺序存取来加载倒排列表了,特别是在使用磁盘驱动器时,这种做法往往能够在数据加载方面增大吞吐量。倒排文件的实现示意图如图1-6 所示。 图1-6 实现倒排文件 ----—————— A 在通过文件系统存储倒排列表时,也可能会遇到文件系统无法为其预留连续存储空间的情况,此时就只能将倒排列表分段存储到多块存储空间上了。等诸位读到了附录部分的动态索引构建时,就能看到我们是如何允许并利用倒排列表的分段存储来努力提升构建索引性能的了。 —————————— 倒排列表的物理布局 单词级别的倒排列表由以下两个要素构成。 文档编号(DocID) 文档中的偏移列表(off1、off2...) 除此以外,各单词在各文档中的出现次数一般也会同时保存。这个次数叫作TF(Term Frequency,词频),常用于计算检索结果的排名等。在实现倒排列表时,大多数情况下要将这些数值以二进制形式、按照如下所示的布局存储为二级存储器上的文本(其中的“,”是为了区分各个数据项而额外加上的)。另外,为了进行高效的检索处理,通常还要先将文档编号和偏移量按升序排列后再存储。 DocID,TF,off1,off2,off3 此时,对于之前例子中对应着search 的倒排列表(D1;3,D2;2),就可以用如下的整数数列表示。 1,1,3,2,1,2 若每个整数都使用4 个字节表示,那么该整数数列将占用24 个字节的二级存储空间。另外,在文档级别的倒排列表中,一般会采用只列出文档编号的布局。 压缩倒排列表 在检索处理中,由于从二级存储器中读取倒排列表经常会占据大部分的检索处理时间,所以在大多数情况下都会保存经过压缩的倒排列表来缩短加载时间。有关压缩方法我们将在第5 章详细讲解。由于倒排列表一般都是整数数列,所以通常会采用适合整数数列的压缩方法。