文件的索引结构.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,文件索引结构与倒排表,1,本讲主要内容：,平衡二叉树,文件的索引结构,倒排表与倒排索引,类型无关的软件平台架构,2,字典的二分查找,二分查找,(binary search),要求：,查找表为有序表，即表中,结点按关键字有序排列，并且采用顺序存储结构。,基本思想：,确定搜索区间的中点位置：,然后将待查的key值与rangemid.key比较：若相等，则查找成功并返回此位置，否则确定新的查找区间，继续二分查找,.,3,动态查找表结构,二叉排序树（又称二叉搜索树）,以,关键码值,为结点的二叉树,如果任一结点的左子树非空，则左子树中的所有结点的关键码都小于根结点的关键码；,如果任一结点的右子树非空，则右子树中的所有结点的关键码都大于根结点的关键码。,10,15,20,40,6,2,8,15,30,25,4,二叉排序树的插入与构造,如果二叉排序树为空，则新结点作为根结点。,如果二叉排序树非空，则将新结点的关键码与根结点的关键码比较，,若相等表示该结点已在二叉排序树中；若小于根结点的关键码，则将新结点插入到根结点的左子树中；,否则，插入到右子树中。,子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到左或右子树为空二叉树，新结点插入成为叶子结点为止。,5,最佳二叉排序树的构造,(1),先将字典元素关键码排序。,(2),对每个关键码按二分法在排序关键码序列中执行检索，将检索中遇到的还未在二叉排序树中的关键码插入二叉排序树中。,按二分查找中所遇到的节点依次插入二叉排序树。,6,举例,（记录二分查找的过程）,对于,K=27,73,10,5,18,41,99,51,25,，构造最佳二叉排序树的过程如下：,首先将它们排序为：,5,，,10,，,18,，,25,，,27,，,41,，,51,，,73,，,99,，,然后从空二叉树出发，在排序的关键码序列中用二分法检索,5,，检索中遇到的结点为,27,10,5,，将这三个结点插入二叉排序树。,再检索第二个结点,10,，遇到的结点为,27,10,，二叉排序树中已经有这两个结点。,再检索第三个结点,18,，,。,得到的插入次序为,27,，,10,，,5,，,18,，,25,，,51,，,41,，,73,，,99,。,7,静态查找表索引结构,score,studentID,name,assignment,finial exam,45,23,周夏司,50,39,46,16,李景文,10,43,47,2,叶佩霖,50,35,48,29,郭舒文,60,51,49,17,杜文杰,60,52,50,9,阮萃茵,70,29,51,3,龙国才,0,35,52,21,陈俊珊,45,45,53,13,李欣怡,75,55,55,4,刘星,50,29,57,28,郭凌典,25,48,59,14,李敏妍,90,74,61,27,唐慰夷,30,49,62,11,吴宇翔,0,47,71,10,何英华,0,51,78,30,梁迪欣,80,69,8,索引,索引,是索引项的集合，一个,索引项,是由一个结点的关键码和该结点的存储位置组成的关联。,索引的实质还是字典，而且是元素类型相同的等长结点的字典。所有关于字典的讨论都适合于索引；所有字典的实现也可以用来组织索引。,9,文件与索引结构,打开一个文件,10,从文本文件中读入数据集合,11,将数据集转换为记录集,12,通过记录的某一项属性值反过来查找到这个记录的存放地址，或者记录对应的关键码。我们称这种索引为倒排索引（,inverted index,）。,13,倒排索引的建立,14,利用函数指针实现,倒排索引的建立,15,包含数据逻辑层的软件架构,数据源,1,数据源,2,数据源,n,数据逻辑层,数据处理层,数据结构及类型,类型化计算,数据对象,XML,文档,+,Style sheet,数据呈现,数据交换,16,动态查找表,平衡二叉排序树,以上的“最佳”二叉排序树，不仅构造的时间代价很大，而且很难动态的保持。通常用于表示一旦构造后就不改动的,静态字典,；,对于,动态字典,，为了能够在进行元素的插入和删除操作时，较快地对二叉排序树进行调整，通常不要求二叉排序树总是保持“最佳的”检索效率，而是希望达到一种比较容易调整的“较佳”的状态。,17,平衡二叉排序树,，,又称,AVL,树，,要求从整体上看，在动态插入或删除后，每个结点的左右子树能够基本保持平衡。不会出现过分倾斜的现象，从而使得平均检索长度保持比较短。,结点右子树高度与左子树高度之差称为该结点的,平衡因子,，平衡二叉排序树中每个结点的平衡因子只能是,1,、,0,或,1,。,18,19,插入的影响,在平衡二叉排序树中插入新结点时，如果新结点插入后不影响其父结点为根的子树高度，则不会破坏整个二叉排序树的平衡；反之，若父结点为根的子树高度增加了，则可能引起一连串的反映。,其结果又有两种可能，一种是在其祖先的某一层上不再影响子二叉排序树的高度，则整个二叉排序树仍然是平衡的；另一种是在其祖先的某一层上破坏了平衡的要求，使整个二叉排序树不再是,AVL,树。,20,最小不平衡子树,处理失去平衡的方法为首先找出,最小不平衡子树,（指离插入结点最近，且以平衡因子绝对值大于,1,的结点为根的子树），,在保证排序树性质的前提下，调整最小不平衡子树中各结点的连接关系，以达到新的平衡。,21,22,AVL,树调整平衡的原则,LL,型调整,破坏平衡的原因是由于在,A,的左子女,(L),的左子树,(L),中插入新结点，使,A,的平衡因子由,-1,变为,-2,而失去平衡。,调整不破坏节点间的序关系。,调整不增加子树的高度。,23,LL-,调整规则,将,A,的左子女,B,提升为新二叉树的根；原来的根,A,连同其右子树,向右下旋转成为,B,的右子树；,B,的原右子树,作为,A,的左子树。,调整后仍保持二叉排序树的性质，而且整个（子）二叉树的高度与插入前相同，因此不会影响包含它的更大（子）二叉树的平衡。,4,2,1,3,7,0,-1,-1,24,RR,型调整,破坏平衡的原因是由于在,A,的右子女,(R),的右子树,(R),中插入结点，使,A,的平衡因子由,1,变为,2,而失去平衡。,调整规则：,与,LL,型的对称。将,A,的右子女,B,提升为新二叉树的根；原来的根,A,连同其左子树向左下旋转成为,B,的左子树；,B,的原左子树作为,A,的右子树。,4,2,8,9,7,0,-1,-1,25,LR,型调整,破坏平衡的原因是由于在,A,的左子女,(L),的右子树,(R),中插入结点，使,A,的平衡因子由,1,变为,2,而失去平衡。,若,、,、,、,全为空树，,C,就是新插入的结点，记为,LR(0),。否则，新结点可能插在,C,的左子树中，也可能插在,C,的右子树中，分别记为,LR(L),和,LR(R),。,26,27,LR-,调整规则,设,C,为,A,的左子女的右子女，将,A,的孙子结点,C,提升为新二叉树的根；原,C,的父结点,B,连同其左子树,向左下旋转成为新根,C,的左子树，原,C,的左子树,成为,B,的右子树；原根,A,连同其右子树,向右下旋转成为新根,C,的右子树，原,C,的右子树,成为,A,的左子树。,4,2,1,3,7,2.5,-1,0,4,2,1,3,7,3.5,-1,0,LR(L),LR(R),28,RL,型调整,破坏平衡的原因是由于在,A,的右子女,(R),的左子树,(L),中插入结点，使,A,的平衡因子由,1,变为,2,而失去平衡。,调整规则,与,LR,型的对称。设,C,为,A,的右子女的左子女，将,A,的孙子结点,C,提升为新二叉树的根，原来,C,的父结点,B,连同其右子树,向右下旋转成为新根,C,的右子树，,C,的原右子树,成为,B,的左子树；原来的根,A,连同其左子树,向左下旋转成为新根,C,的左子树，原来,C,的左子树,成为,A,的右子树。,29,30,调整控制在最小不平衡子树内,上述所有的调整操作中，,A,为根的最小不平衡子树的高度在插入结点之前和调整之后相同，对,A,为根的子树之外的其它结点的平衡性无影响，调整后二叉排序树成为平衡二叉排序树。,31,元素的删除,与二叉排序树中的结点删除类似，首先找到被删除的结点，如果它不是叶结点，也需要根据二叉排序树的要求转换成一个叶结点的删除。不同之处在于：为了保持删除后的二叉树是平衡的，必须参考插入时的调整方案设计删除后调整的算法；仅仅从最小不平衡子树的调整来看，它与插入时的调整类似，但困难的是：对最小不平衡子树的调整，可能降低它的高度，所以又可能产生更大的最小不平衡子树。因此可能需要反复多次调整。,32,索引文件,多分树,如果文件很大，索引顺序文件的索引可以采用多级索引结构以提高检索的效率。,即为主文件建立了索引之后，又针对本级索引所占的每一个页块建立一个索引项，用这些索引项构成索引的索引。如果新建的这一级索引仍然占用多个页块，则再为它建立索引。这样可以得到一种多级索引结构,多分树。,如果每个内部结点（根除外）有个子女，则称为分树。,33,多分树与索引文件,如果文件很大，索引顺序文件的索引可以采用,多级索引结构,以提高检索的效率。,即为主文件建立了索引之后，又针对本级索引所占的每一个页块建立一个索引项，用这些索引项构成索引的索引。如果新建的这一级索引仍然占用多个页块，则再为它建立索引。这样可以得到一种多级索引结构,多分树,。,如果每个内部结点（根除外）有个子女，则称为,分树,。,34,表示方法,多分树的每个结点分配一个页块，结点上的信息是许多二元组（，）的序列，它们在结点内按关键码的值排序。,第个二元组中的是本结点的第个子结点（页块）的地址，是这个子结点上的最小（或者最大）关键码。,多分树的叶结点就是主文件的最底层索引。,主文件的每个页块可以看成是多分树的外部结点。,35,36,索引检索,要检索一个关键码为的记录，则读入根结点的页块，在这个页块上找到最后一个满足的索引项（，），读入所指的下一级索引的页块。这样一级一级地进行，直到读入主文件页块，在其上查找关键码为的记录。,37,索引插入,在这种文件上插入记录是不太方便的。为了使主文件的记录保持关键码递增的次序，需要把插入位置之后的每个记录向后移动，从而导致增加新的索引项和索引页块，需要对外存上的页块进行大量的调整。,多分树主要实用于静态的索引顺序文件，对于经常需要插入和删除的动态索引顺序文件，需要采用动态索引结构，即下面要讨论的树和,树,38,B,树,一棵,m,阶的,B,树满足下列条件,1,，,每个结点至多有,m,棵子树。,2,，除根结点外，其它每个分支结点至少有,棵子树。,3,，根结点至少有两棵子树,(,除非,B,树只包含一个结点,),。,4,，,所有叶结点在同一层上。,B,树的叶结点可以看成一种外部结点，不包含任何信息。,5,，,有,j,个孩子的非叶结点恰好有,j-1,个关键码，关键码按递增次序排列。,39,#define m 1024,struct BTNode;,typedef struct BTNode*PBTNode;,struct BTNode ,int keyNum;/*,实际关键字个数，,keyNumm*/,PBTNode parent;/*,指向父结点*,/,PBTNode *ptr;/*,子树指针向量,:ptr0ptrkeyNum*/,KeyType *key;/*,关键字向量,:key 0key keyNum,1*/,typedef struct BTNode*BTree;,typedef BTree*PBTree;,B,树的类型和结点类型定义：,40,B,树的运算,检索,插入,删除,41,检索,在,B,树中检索关键码,key,的思路,根据要查找的关键码,key,，在根结点的关键码集合中进行顺序或二分法检索，若,key=k,i,，则检索成功；否则，,key,一定在某,k,i,和,k,i+1,之间，取指针,p,i,所指结点继续查找，重复上述检索过程，直到检索成功，或指针,p,i,为空，检索失败。,42,在以下,B,树中检索关键码为,400,的结点,43,在,B,树中插入关键码,key,的思路,对高度为,h,的,m,阶,B,树，新结点一般是插在第,h,层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论：,1,，若该结点中关键码个数小于,m-1,，则直接插入即可。,2,，若该结点中关键码个数等于,m-1,，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点（,h-1,层）中；,重复上述工作，最坏情况一直分裂到根结点，建立一个新的根结点，整个,B,树增加一层。,44,在以下,B,树中插入关键码,200,、,460,45,46,47,在,B,树中删除关键码,key,的思路,48,7.6.3 B+,树,一个,m,阶的,B+,树满足下列条件,1,、,每个结点至多有,m,棵子树。,2,、除根结点外，其它每个分支至少有,棵子树,3,、非叶结点的根结点至少有两棵子树。,4,、叶结点都在同一层中。,49,说明,（,1,）,有,j,棵子树的结点有,j,个关键码，它们按照递增次序排列。,（,2,）,每个叶结点中至少包含 个关键码。所有主文件记录的索引项都存放在,B+,树的叶结点中。,（,3,）,所有分支结点可看成是索引的索引。结点中仅包含它的各个子结点中最大,(,或最小,),关键码的分界值及指向子结点的指针。,50,B+,树和,B,树的差异：,（,1,）,B+,树有,n,棵子树的结点中含有,n,个关键码；而,B,树有,n,棵子树的结点中含有,n,-1,个关键码。,（,2,）,B+,树所有的叶子结点中包含了完整的索引的信息，而,B,树中非叶结点的关键码与叶结点的关键码均不重复，它们共同构成全部索引信息。,（,3,）,B+,树所有的非叶结点可以看成是高层索引，结点中仅含有其子树中最大（或最小）关键码,.,51,B+,树的运算,检索,在,B,树中检索关键码,key,的方法与,B,树的检索方式相似，但若在分支结点上找到检索的关键码时，检索并不结束，要继续找到,B+,树的叶结点为止。,52,插入,与,B,树的插入操作相似，总是插在叶结点上。当结点中原关键码个数等于,m,时，该结点分裂成两个结点，分别使关键码个数为,和 。,删除,仅在叶结点删除关键码。若因删除操作使结点中关键码数少于 时，则从兄弟结点调整或者合并。合并的过程和,B,树相似，区别是父结点中作为分界的关键码，不放入合并后的结点中。,53,B+,树在索引顺序文件中的应用,B+,树可以表示主文件的密集索引，也可以表示稀疏索引，以稀疏索引为例：,通常在,B+,树表示的索引顺序文件中设两个头指针一个指向,B+,树的根结点，另一个指向主文件中关键码最小的页块，所有主文件的页块顺序链成单链表。,在索引顺序文件中可以采用两种检索方式一种直接从最小关键码开始顺序检索；另一种从,B+,树的根结点开始逐层检索。,当主文件中需要增加或减少一个页块时，只需在,B+,树中为之插入或删除一个索引项，问题归结为,B+,树本身的运算。,54,55,B+,树的主要优点,B+,树可以比,B,树更快地实现检索：同样大的字典，用,B+,树组织索引的层数比,B,树的索引层数少。,另外，由于,B+,树所有的叶子结点中包含了完整的索引的信息，可以比较方便的表示文件的稀疏索引。,最后，,B,树的检索，插入和删除统一在叶结点上进行，比,B,树相对简单。,56,作业：算法设计,有重复键值倒排索引的建立、使用（访问）与维护。假设按特定字段值能访问到记录的,id,号就算正确访问到该记录。可以使用网页上提供的,student.txt,为例。,数据结构设计。建立算法。插入删除算法。访问算法。,算法效率分析（最坏情况、平均情况）。,适用范围与应用场景分析。,包含对本设计的总体评价。,提交：,word,文档。,16,号。,57,