文件的索引结构2

《文件的索引结构2》由会员分享，可在线阅读，更多相关《文件的索引结构2（57页珍藏版）》请在金锄头文库上搜索。

1、文件索引结构与倒排表,2007/05/14,2,本讲主要内容：,平衡二叉树 文件的索引结构 倒排表与倒排索引 类型无关的软件平台架构,3,字典的二分查找,二分查找(binary search) 要求： 查找表为有序表，即表中 结点按关键字有序排列，并且采用顺序存储结构。 基本思想： 确定搜索区间的中点位置： 然后将待查的key值与rangemid.key比较：若相等，则查找成功并返回此位置，否则确定新的查找区间，继续二分查找.,4,动态查找表结构 二叉排序树（又称二叉搜索树）,以关键码值为结点的二叉树 如果任一结点的左子树非空，则左子树中的所有结点的关键码都小于根结点的关键码； 如果任一结点的

2、右子树非空，则右子树中的所有结点的关键码都大于根结点的关键码。,5,二叉排序树的插入与构造,如果二叉排序树为空，则新结点作为根结点。 如果二叉排序树非空，则将新结点的关键码与根结点的关键码比较， 若相等表示该结点已在二叉排序树中；若小于根结点的关键码，则将新结点插入到根结点的左子树中； 否则，插入到右子树中。 子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到左或右子树为空二叉树，新结点插入成为叶子结点为止。,6,最佳二叉排序树的构造,(1) 先将字典元素关键码排序。 (2) 对每个关键码按二分法在排序关键码序列中执行检索，将检索中遇到的还未在二叉排序树中的关键码插入

3、二叉排序树中。 按二分查找中所遇到的节点依次插入二叉排序树。,7,举例（记录二分查找的过程）,对于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。,8,静态查找表索引结构,9,索引,索引是索引项的

4、集合，一个索引项是由一个结点的关键码和该结点的存储位置组成的关联。 索引的实质还是字典，而且是元素类型相同的等长结点的字典。所有关于字典的讨论都适合于索引；所有字典的实现也可以用来组织索引。,10,文件与索引结构 打开一个文件,11,从文本文件中读入数据集合,12,将数据集转换为记录集,13,通过记录的某一项属性值反过来查找到这个记录的存放地址，或者记录对应的关键码。我们称这种索引为倒排索引（inverted index）。,14,倒排索引的建立,15,利用函数指针实现 倒排索引的建立,16,包含数据逻辑层的软件架构,数据源1,数据源2,数据源n,数据逻辑层,数据处理层,数据结构及类型,类型化

5、计算,数据对象,XML 文档,+,Style sheet,数据呈现 数据交换,17,动态查找表 平衡二叉排序树,以上的“最佳”二叉排序树，不仅构造的时间代价很大，而且很难动态的保持。通常用于表示一旦构造后就不改动的静态字典； 对于动态字典，为了能够在进行元素的插入和删除操作时，较快地对二叉排序树进行调整，通常不要求二叉排序树总是保持“最佳的”检索效率，而是希望达到一种比较容易调整的“较佳”的状态。,18,平衡二叉排序树，,又称AVL树，要求从整体上看，在动态插入或删除后，每个结点的左右子树能够基本保持平衡。不会出现过分倾斜的现象，从而使得平均检索长度保持比较短。 结点右子树高度与左子树高度之差

6、称为该结点的平衡因子，平衡二叉排序树中每个结点的平衡因子只能是1、0或1。,19,20,插入的影响,在平衡二叉排序树中插入新结点时，如果新结点插入后不影响其父结点为根的子树高度，则不会破坏整个二叉排序树的平衡；反之，若父结点为根的子树高度增加了，则可能引起一连串的反映。 其结果又有两种可能，一种是在其祖先的某一层上不再影响子二叉排序树的高度，则整个二叉排序树仍然是平衡的；另一种是在其祖先的某一层上破坏了平衡的要求，使整个二叉排序树不再是AVL树。,21,最小不平衡子树,处理失去平衡的方法为首先找出最小不平衡子树（指离插入结点最近，且以平衡因子绝对值大于1的结点为根的子树）， 在保证排序树性质的

7、前提下，调整最小不平衡子树中各结点的连接关系，以达到新的平衡。,22,23,AVL树调整平衡的原则,LL型调整 破坏平衡的原因是由于在A的左子女(L)的左子树(L)中插入新结点，使A的平衡因子由 -1变为 -2而失去平衡。,调整不破坏节点间的序关系。 调整不增加子树的高度。,24,LL-调整规则,将A的左子女B提升为新二叉树的根；原来的根A连同其右子树向右下旋转成为B的右子树；B的原右子树作为A的左子树。 调整后仍保持二叉排序树的性质，而且整个（子）二叉树的高度与插入前相同，因此不会影响包含它的更大（子）二叉树的平衡。,4,-1,-1,25,RR型调整,破坏平衡的原因是由于在A的右子女(R)的

8、右子树(R)中插入结点，使A的平衡因子由1变为2而失去平衡。 调整规则：与LL型的对称。将A的右子女B提升为新二叉树的根；原来的根A连同其左子树向左下旋转成为B的左子树；B的原左子树作为A的右子树。,4,-1,-1,26,LR型调整,破坏平衡的原因是由于在A的左子女(L)的右子树(R)中插入结点，使A的平衡因子由1变为2而失去平衡。 若、全为空树，C就是新插入的结点，记为LR(0)。否则，新结点可能插在C的左子树中，也可能插在C的右子树中，分别记为LR(L)和LR(R)。,27,28,LR-调整规则,设C为A的左子女的右子女，将A的孙子结点C提升为新二叉树的根；原C的父结点B连同其左子树向左下

9、旋转成为新根C的左子树，原C的左子树成为B的右子树；原根A连同其右子树向右下旋转成为新根C的右子树，原C的右子树成为A的左子树。,4,-1,0,4,-1,0,LR(L),LR(R),29,RL型调整,破坏平衡的原因是由于在A的右子女(R)的左子树(L)中插入结点，使A的平衡因子由1变为2而失去平衡。 调整规则与LR型的对称。设C为A的右子女的左子女，将A的孙子结点C提升为新二叉树的根，原来C的父结点B连同其右子树向右下旋转成为新根C的右子树，C的原右子树成为B的左子树；原来的根A连同其左子树向左下旋转成为新根C的左子树，原来C的左子树成为A的右子树。,30,31,调整控制在最小不平衡子树内,上

10、述所有的调整操作中，A为根的最小不平衡子树的高度在插入结点之前和调整之后相同，对A为根的子树之外的其它结点的平衡性无影响，调整后二叉排序树成为平衡二叉排序树。,32,元素的删除,与二叉排序树中的结点删除类似，首先找到被删除的结点，如果它不是叶结点，也需要根据二叉排序树的要求转换成一个叶结点的删除。不同之处在于：为了保持删除后的二叉树是平衡的，必须参考插入时的调整方案设计删除后调整的算法；仅仅从最小不平衡子树的调整来看，它与插入时的调整类似，但困难的是：对最小不平衡子树的调整，可能降低它的高度，所以又可能产生更大的最小不平衡子树。因此可能需要反复多次调整。,33,索引文件 多分树,如果文件很大，

11、索引顺序文件的索引可以采用多级索引结构以提高检索的效率。 即为主文件建立了索引之后，又针对本级索引所占的每一个页块建立一个索引项，用这些索引项构成索引的索引。如果新建的这一级索引仍然占用多个页块，则再为它建立索引。这样可以得到一种多级索引结构多分树。 如果每个内部结点（根除外）有个子女，则称为分树。,34,多分树与索引文件,如果文件很大，索引顺序文件的索引可以采用多级索引结构以提高检索的效率。 即为主文件建立了索引之后，又针对本级索引所占的每一个页块建立一个索引项，用这些索引项构成索引的索引。如果新建的这一级索引仍然占用多个页块，则再为它建立索引。这样可以得到一种多级索引结构多分树。 如果每个

12、内部结点（根除外）有个子女，则称为分树。,35,表示方法,多分树的每个结点分配一个页块，结点上的信息是许多二元组（，）的序列，它们在结点内按关键码的值排序。 第个二元组中的是本结点的第个子结点（页块）的地址，是这个子结点上的最小（或者最大）关键码。 多分树的叶结点就是主文件的最底层索引。 主文件的每个页块可以看成是多分树的外部结点。,36,37,索引检索,要检索一个关键码为的记录，则读入根结点的页块，在这个页块上找到最后一个满足的索引项（，），读入所指的下一级索引的页块。这样一级一级地进行，直到读入主文件页块，在其上查找关键码为的记录。,38,索引插入,在这种文件上插入记录是不太方便的。为了使

13、主文件的记录保持关键码递增的次序，需要把插入位置之后的每个记录向后移动，从而导致增加新的索引项和索引页块，需要对外存上的页块进行大量的调整。 多分树主要实用于静态的索引顺序文件，对于经常需要插入和删除的动态索引顺序文件，需要采用动态索引结构，即下面要讨论的树和树,39,B树,一棵m阶的B树满足下列条件 1，每个结点至多有m棵子树。 2，除根结点外，其它每个分支结点至少有 棵子树。 3，根结点至少有两棵子树(除非B树只包含一个结点)。 4，所有叶结点在同一层上。B树的叶结点可以看成一种外部结点，不包含任何信息。 5，有j个孩子的非叶结点恰好有j-1个关键码，关键码按递增次序排列。,40,#def

14、ine m 1024 struct BTNode; typedef struct BTNode * PBTNode; struct BTNode int keyNum; /* 实际关键字个数，keyNumm */ PBTNode parent; /* 指向父结点 */ PBTNode *ptr; /* 子树指针向量: ptr0ptrkeyNum */ KeyType *key; /* 关键字向量: key 0key keyNum1 */ typedef struct BTNode *BTree; typedef BTree * PBTree;,B树的类型和结点类型定义：,41,B树的运算,检索

15、 插入 删除,42,检索 在B树中检索关键码key的思路,根据要查找的关键码key，在根结点的关键码集合中进行顺序或二分法检索，若key=ki，则检索成功；否则，key一定在某ki和ki+1之间，取指针pi所指结点继续查找，重复上述检索过程，直到检索成功，或指针pi为空，检索失败。,43,在以下B树中检索关键码为400的结点,44,在B树中插入关键码key的思路,对高度为h的m阶B树，新结点一般是插在第h层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论： 1，若该结点中关键码个数小于m-1，则直接插入即可。 2，若该结点中关键码个数等于m-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点（h-1层）中； 重复上述工作，最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层。,45,在以下B树中插入关键码200、460,46,47,48,在B树中删除关键码key的思路,49,7.6.3 B+树,一个m阶的B+树满足下列条件 1、每个结点至多有m棵子树。 2、除根结点外，其它每个分支至少有 棵子树 3、非叶结点的根结点至少有两棵子树。 4、叶结点都在同一层中。,50,说明,（1）有j棵子树