索引和散列学习(一)

索引和散列学习(一)--静态索引结构

索引结构和散列结构是用在外部搜索的搜索结构。

数据在外存中的组织的方式也就是文件结构，主要分成顺序、直接存取(散列)、和索引结构。

在文件组织中主要使用的是索引和散列方法。

下面是殷人昆老师的书中介绍的索引结构

静态索引结构

当数据对象个数 n 很大时，如果用无序表形式的静态搜索结构存储，采用顺序搜索，则搜索效率极低。如果采用有序表存储形式的静态搜索结构，则插入新记录进行排序，时间开销也很可观。这时可采用索引方法来实现存储和搜索。

线性索引 (Linear Index List)

线性索引分成两种:稠密索引和稀疏索引。

稠密索引

一个索引项(位于索引表)对应数据表中一个对象的索引结构。当对象在外存中按加入顺序存放而不是按关键码有序存放时必须采用稠密索引结构，这时的索引结构叫做索引非顺序结构。

例如下图:

稀疏索引

当对象在外存中有序存放时，可以把所有 n 个对象分为 b 个子表(块)存放，一个索引项对应数据表中一组对象(子表).在子表中,  所有对象可能按关键码有序地存放,  也可能无序地存放。但所有这些子表必须分块有序，后一个子表中所有对象的关键码均大于前一个子表中所有对象的关键码。它们都存放在数据区中。另外建立一个索引表。索引表中每一表目叫做索引项，它记录了子表中最大关键码max_key以及该子表在数据区中的起始位置obj_addr。见下图所示:

各个索引项在索引表中的序号与各个子表的块号有一一对应的关系：第 i 个索引项是第 i 个子表的索引项,  i = 0, 1, …, n-1。这样的索引结构叫做索引顺序结构。

对索引顺序结构进行搜索时，一般分为两级搜索。

(1)先在索引表 ID 中搜索给定值 K，确定满足 ID[i-1].max_key < K <=ID[i].max_key 的 i 值，即待查对象可能在的子表的序号。

(2)然后再在第 i 个子表中按给定值搜索要求的对象。

索引表是按max_key有序的，且长度也不大，可以对分搜索，也可以顺序搜索。

各子表内各个对象如果也按对象关键码有序，可以采用对分搜索或顺序搜索；如果不是按对象关键码有序，只能顺序搜索。

倒排表

基于属性的倒排

在一个带结构的记录文件中，如数据库文件等。文件里存放的都是一条接着一条的整齐的记录，每个记录又可分为一个个的属性。检索过程往往要求找出，在某个或者某些属性上满足一定条件的记录集合。像这一类的检索我们称为基于属性的检索。

对包含有大量数据对象的数据表或文件进行搜索时，最常用的是针对对象的主关键码建立索引。主关键码可以唯一地标识该对象。用主关键码建立的索引叫做主索引。

主索引的每个索引项给出对象的关键码和对象在表或文件中的存放地址。

对象关键码key

对象的存储地址addr

在实际应用中有时需要针对其它属性进行搜索。例如，查询如下的职工信息：

(1) 列出所有教师的名单；

(2) 已婚的女性职工有哪些人？

这些信息在数据表或文件中都存在，但都不是关键码，为回答以上问题，只能到表或文件中去顺序搜索，搜索效率极低。

因此，除主关键码外，可以把一些经常搜索的属性设定为次关键码，并针对每一个作为次关键码的属性，建立次索引。

在次索引中，列出该属性的所有取值(次关键码)，并对每一个取值建立有序链表，把所有具有相同属性值的对象按存放地址递增的顺序或按主关键码递增的顺序链接在一起。

次索引的索引项由次关键码、链表长度和链表本身等三部分组成。

为了回答上述的查询，我们可以分别建立“性别”、“婚否”和“职务”次索引

倒排表或倒排文件是一种次索引的实现。在倒排表中所有次关键码的链都保存在次索引中，仅通过搜索次索引就能找到所有具有相同属性值的对象。

在次索引中记录对象存放位置的指针可以用主关键码表示，可以通过搜索次索引确定该对象的主关键码，再通过搜索主索引确定对象的存放地址。

有了倒排文件，我们就可以将查询变成几个集合之间的交，并等运算，得到的最后结果即时我们要求的，这样不用挨个读取记录，且参与运算的数据大大减少，基本可以不用多次读写磁盘而直接在内存里进行运算，大大提高了检索速度。

基于文本的倒排

倒排文件也可以应用于非结构化的信息检索里面，如大量正文的文本索引。尤其当今搜索引擎需要对海量的正文文本信息进行检索的情况下，倒排文件的使用尤其重要。

 对多个正文文本建立索引的基本思想就是，把正文看成一个一个的关键词的集合，然后用这些词组成一些适合快速检索的数据结构。一个倒排文件就是一个已经排好序的关键词的列表，其中每个关键词指向一个倒排表，该表中记录了该关键词出现的文档集合以及在该文档中的出现位置。如北大某院图书馆论文集的部分倒排表：

关键词	倒排表（所在文档编号，出现次数， 出现位置）
KMP	（#3307, 2, 5, 43）（#4615, 3, 0, 19, 34, 70, 143）
最小支撑树	（#2519, 1, 267）（#6742, 3, 19, 322, 526）……
贪心算法	（#2948, 3, 45, 267, 587）（#3693, 5, 39, 423, 765,809,1024）……
……	……

这样一来，当要检索关于KMP方面的文章时，可直接取出其倒排表即可得知，编号为3307和4615的文章都是包含KMP这 个关键词的，且能知道包含了多少次，以及在各个文档中的具体出现位置。如果同时需要“最小支撑树”和“贪心算法”两方面的文章，则可以直接将两个倒排表取 交集，就能得到所有符合条件的集合。如此可以免去在整个图书馆里每一篇文档里去逐个查找的代价，从而可以轻松快捷的得到结果。

对于这样一个正文倒排文件的建立通常需要如下几个步骤。首先是文本切词(分词)，即以人工或者机器自动的方式把一篇文档里的可能成为关键词的词组划分出来。在汉语等东方语言中，因为词与词之间没有空格，所以怎样把词组从句子中完整的切分出来，需要专门的研究。这需要自然语言理解技术(natural language processing,属人工智能研究的一个分支)的支持。然后是得到各个关键词的集合，对于每个关键词建立它的倒排表，然后把所有倒排表按关键词排序存入文件，形成倒排文件。文件中除了记录那个关键词对应 哪些文档外，还应该有关键词在文档中的出现位置和出现次数等。然而最后得到的倒排文件往往还是很大，关键词很多，所以还需要对倒排文件里的关键词再次建立索引结构。对关键词进行索引的常用技术有散列和B+树等，当然如果关键词能全部放入内存，也可以使用二叉查找树来建立索引。

 由于倒排索引支持高效检索，所以应用相当广泛。当然，对倒排表进行集合运算也需要一些运算空间，更大的缺点在于，当文件发生变化时，要同时维护更新这些索引，而这种更新的工作量会很大，所以它比较适合于当大文件里面内容比较稳定的情况下。尤其像光盘上的数据检索等就会是它最理想的应用场所之一。

m路静态搜索树

当数据对象数目特别大，索引表本身也很大，在内存中放不下，需要分批多次读取外存才能把索引表搜索一遍。

在此情况下，可以建立索引的索引，称为二级索引。二级索引可以常驻内存，二级索引中一个索引项对应一个索引块，登记该索引块的最大关键码及该索引块的存储地址。

如果二级索引在内存中也放不下，需要分为许多块多次从外存读入。可以建立二级索引的索引，叫做三级索引。这时，访问外存次数等于读入索引次数再加上1次读取对象。

这种多级索引结构形成一种 m 叉树。树中每一个分支结点表示一个索引块，它最多存放 m 个索引项，每个索引项分别给出各子树结点 (低一级索引块) 的最大关键码和结点地址。

树的叶结点中各索引项给出在数据表中存放的对象的关键码和存放地址。这种m叉树用来作为多级索引，就是m路搜索树。

m路搜索树可能是静态索引结构，即结构在初始创建，数据装入时就已经定型，在整个运行期间，树的结构不发生变化。

m路搜索树还可能是动态索引结构，即在整个系统运行期间，树的结构随数据的增删及时调整，以保持最佳的搜索效率。