oracle辅助索引（二）

lyd2004888

　　3、辅助索引中的间接
　　图4-15所示结构存在空间浪费，有时浪费很大。假如某个索引键值在数据文件中出现n次，那么这个键值在索引文件中就要写n次，如果我们只为指向该键值的所有指针存储一次键值，这样就会比较好。
　　避免键值重复的一种简便方法是使用一个称为桶的间接层，它介于辅助索引文件和数据文件之间。如图4-17所示，每个查找键K有一个键-指针对，指针指向一个桶文件，该文件中存放K的桶。从这个位置开始，直到索引指向的下一个位置，其间指针指向索引键值为K的所有记录。
　　例4.15 例如在图4-17的索引文件中，沿索引键为50的索引项指针找到中间“桶”文件。这一指针刚好将我们带到桶文件中第一个块的最后一个指针。继续向前查找，找到下一块的第一个指针。因为索引文件中键值为60的索引项指针刚好指向桶文件的第二个块的第二个指针，所以我们停止查找。
　　在图4-17所示的方式中，只要查找键值的存储空间比指针大就可以节省空间。不过，即使在键值和指针大小相当的情况下，在辅助索引上使用间接也有一个重要的好处：我们通常可以在不访问数据文件记录的前提下利用桶的指针来帮助回答一些查询。特别是，当查询有多个条件，而每个条件都有一个可用的辅助索引时，我们可以通过在主存中将指针集合求交来找到满足所有条件的指针，然后只需要检索交集中指针指向的记录。这样，我们就节省了检索满足部分条件而非所有条件的记录所需的I/O开销。

　　例4.16 考虑例4.14中的关系
　　Movie（title,year,length,stadioName）
　　假定我们在studioName和year上都建立了有间接桶的辅助索引，而且我们要执行如下查询：

　　select>　　from Movie
　　where studioName = 'Disney' and
　　year = 1995;
　　即：找出Disney在1995年制作的所有电影。
　　图4-18说明了如何使用索引来回答这个查询。通过studioName上的索引，我们找出了所有指向Disney制作的电影的指针。但是，我们并不把这些记录从磁盘上取到主存中，而是通过year上的索引，再找出所有指向1995年制作的电影的指针。然后我们求两个指针集的交集，正好得到1995年Disney制作的所有电影。现在我们到磁盘上去检索所有包含一部或几部这样的电影的块，这样只需检索尽可能少的数据块。

　　4、文档检索和倒排索引
　　多年来，信息检索界都在处理文档的存储和按关键字集高效检索文档的问题。随着WWW的出现以及在线保存所有文档成为可能，基于关键字的文档检索已成为数据库最大的难题之一。
　　尽管可用来找出相关的文档的查询有许多种，但最简单、最常见的形式可用关系的术语描述为：
　　（1）一个文档可被看成是关系Doc的元组。这个关系有很多属性，每个属性对应于文档可能出现的一个词。每个属性都是布尔型—表明该词在该文档出现还是没有出现。因此，这一
　　关系模式可以被看作：
　　Doc（hascat,hasDog,）
　　其中hascat取值为真当且仅当该文档中至少出现一次“cat”这个词。
　　（2）关系Doc的每个属性上都建有辅助索引。不过，我们不必费心为属性值为FALSE的元组建索引项；相反，索引只会将我们带到出现该词的那些文档，即，索引中只有查找键值为TRUE的索引项。
　　（3）我们不是给每个属性（即每个词）建立一个单独的索引，而是把所有的索引合成一个，称为倒排索引。这个索引使用间接桶来提高空间利用率，正如4.2.3节中讨论的那样。
　　例4.17 图4-19所示为一个倒排索引。取代记录数据文件的是一个文档集合，每个文档可以被存放在一个或多个磁盘块上。倒排索引本身由一系列词-指针对组成；词实际上是索引的查找键。正如到目前为止讨论的任何一种索引那样，倒排索引被存储在连续的块中。不过，在一些文档检索应用中，数据的变化不像典型数据库中那样频繁，因而通常也就不用提供应付块溢出或索引变化的措施。

　　指针指向“桶”文件中的位置。例如，在图4-19中，“cat”一词有一个指针指向桶文件。该指针在桶文件中指明的位置之后是所有包含“cat”的文档的指针。图中给出了一些这样的指针。类似地，图中“dog”一词的指针指向一个指针列表，该列表中的指针指向包含“dog”的所有文档。
　　桶文件中的指针可以是：
　　1）指向文档本身的指针。
　　2）指向词的某一次出现的指针。在这种情况下，指针可以是由文档的第一个块和一个表示该词在文档中出现次数的整数构成的对。
　　一旦有了使用这种由指向词的每次出现的指针桶的想法，我们可能就会想扩展这个想法，使桶数组包含更多有关词的出现的信息。这样，桶文件本身就成了有重要结构的记录集合。这种做法的早期应用是区分一个词出现在文档的题目、摘要，还是正文中。随着Web上文档的增长，尤其是使用HTML、XML或其他标记语言的文档的增长，我们也可以指明与词关联的标记。例如，我们不仅可以区分出现在题头、表或锚中的词，而且可以区分以不同字体和字号出现的词。
　　========================对信息检索的进一步讨论============================
　　有很多技术可用于改进基于关键字的文档检索效率。完整介绍这些技术已超出本书的范围，这里介绍两种有用的技术：
　　1）抽取词干。在将单词的出现放入索引中之前。我们删除词的后缀以找出它的“词干”。例如，复数名词可被当作其单数形式处理。因此，例4.17中的倒排索引显然使用了抽取词干技术，因为搜索“dog”一词时我们不仅得到“dog”的文档，而且得到一个有单词“dogs”的文档。
　　2）无用词。像“the”、“and”之类最常用的词称为无用词，通常不包含在倒排索引中。原因在于好几百个常用词出现在太多的文档中，以至于它根本无益于检索特定主题。去除无用词还可以明显地缩小索引。
　　============================================================================
　　例4.18 图4-20所示为一个标明HTML文档中词的出现情况的桶文件。如果有出现类型即标记的，就在第一列指明。第二、第三列一起构成指针指向词的出现。第三列指明文档，而第二列给出了该文档中该词出现的次数。

　　可以用这种数据结构来回答关于文档的各种查询，而且不用仔细查看文档。例如，假设我们想找出有关狗的，并将狗与猫做了比较的文档；没有深刻理解文档的内容，我们就无法准确地回答这个查询。但是，要是查找符合以下条件的文档，我们可以获得一个很好的提示：
　　a）在标题（title）中提到狗，且
　　b）在某个锚中提到猫—该锚可能是连到一个关于猫的文档的链接。
　　==================================桶中的插入与删除==============================
　　在一些图如图4-19中，我们所给的桶是大小适中的紧凑数给。实际上，它们是单个字段指针）的记录，且像其他任何记录集合一样存放在块中。因此在插入和删除指针时，我们可用到目前为止学过的任一种技术，例如为文件的扩充预留空闲空间、溢出块和可能的块内或块间记录移动。在后一种情况下，当我们移动例排索引的桶中指针指向的记录时，必须小心地改变从倒排索引到桶文件中的相应指针。
　　===============================================================================
　　我们可用通过对指针求交来回答这个查询。也就是说，按对应于“cat”的指针找到这一单词的所有出现。我们从桶文件中选择有“cat”出现且类型为“锚”的文档指针。接着，我们找到“dog”的桶中项目，并从中选择类型为“标题”的文档指针。如果把这两个指针集相交，就得到符合在标题中提到“dog”且在某个锚中提到“cat”这一条件的文档.
　　oracle视频教程请关注:http://u.youku.com/user_video/id_UMzAzMjkxMjE2.html