文件的索引结构【技术材料】.ppt
《文件的索引结构【技术材料】.ppt》由会员分享,可在线阅读,更多相关《文件的索引结构【技术材料】.ppt(57页珍藏版)》请在三一文库上搜索。
1、文件索引结构与倒排表,2007/05/14,1,技术课件,本讲主要内容:,平衡二叉树 文件的索引结构 倒排表与倒排索引 类型无关的软件平台架构,2,技术课件,字典的二分查找,二分查找(binary search) 要求: 查找表为有序表,即表中 结点按关键字有序排列,并且采用顺序存储结构。 基本思想: 确定搜索区间的中点位置: 然后将待查的key值与rangemid.key比较:若相等,则查找成功并返回此位置,否则确定新的查找区间,继续二分查找.,3,技术课件,动态查找表结构 二叉排序树(又称二叉搜索树),以关键码值为结点的二叉树 如果任一结点的左子树非空,则左子树中的所有结点的关键码都小于根
2、结点的关键码; 如果任一结点的右子树非空,则右子树中的所有结点的关键码都大于根结点的关键码。,4,技术课件,二叉排序树的插入与构造,如果二叉排序树为空,则新结点作为根结点。 如果二叉排序树非空,则将新结点的关键码与根结点的关键码比较, 若相等表示该结点已在二叉排序树中;若小于根结点的关键码,则将新结点插入到根结点的左子树中; 否则,插入到右子树中。 子树中的插入过程和树中的插入过程相同,如此进行下去,直到找到该结点,或者直到左或右子树为空二叉树,新结点插入成为叶子结点为止。,5,技术课件,最佳二叉排序树的构造,(1) 先将字典元素关键码排序。 (2) 对每个关键码按二分法在排序关键码序列中执行
3、检索,将检索中遇到的还未在二叉排序树中的关键码插入二叉排序树中。 按二分查找中所遇到的节点依次插入二叉排序树。,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,7
4、3,99。,7,技术课件,静态查找表索引结构,8,技术课件,索引,索引是索引项的集合,一个索引项是由一个结点的关键码和该结点的存储位置组成的关联。 索引的实质还是字典,而且是元素类型相同的等长结点的字典。所有关于字典的讨论都适合于索引;所有字典的实现也可以用来组织索引。,9,技术课件,文件与索引结构 打开一个文件,10,技术课件,从文本文件中读入数据集合,11,技术课件,将数据集转换为记录集,12,技术课件,通过记录的某一项属性值反过来查找到这个记录的存放地址,或者记录对应的关键码。我们称这种索引为倒排索引(inverted index)。,13,技术课件,倒排索引的建立,14,技术课件,利用
5、函数指针实现 倒排索引的建立,15,技术课件,包含数据逻辑层的软件架构,数据源1,数据源2,数据源n,数据逻辑层,数据处理层,数据结构及类型,类型化计算,数据对象,XML 文档,+,Style sheet,数据呈现 数据交换,16,技术课件,动态查找表 平衡二叉排序树,以上的“最佳”二叉排序树,不仅构造的时间代价很大,而且很难动态的保持。通常用于表示一旦构造后就不改动的静态字典; 对于动态字典,为了能够在进行元素的插入和删除操作时,较快地对二叉排序树进行调整,通常不要求二叉排序树总是保持“最佳的”检索效率,而是希望达到一种比较容易调整的“较佳”的状态。,17,技术课件,平衡二叉排序树,,又称A
6、VL树,要求从整体上看,在动态插入或删除后,每个结点的左右子树能够基本保持平衡。不会出现过分倾斜的现象,从而使得平均检索长度保持比较短。 结点右子树高度与左子树高度之差称为该结点的平衡因子,平衡二叉排序树中每个结点的平衡因子只能是1、0或1。,18,技术课件,19,技术课件,插入的影响,在平衡二叉排序树中插入新结点时,如果新结点插入后不影响其父结点为根的子树高度,则不会破坏整个二叉排序树的平衡;反之,若父结点为根的子树高度增加了,则可能引起一连串的反映。 其结果又有两种可能,一种是在其祖先的某一层上不再影响子二叉排序树的高度,则整个二叉排序树仍然是平衡的;另一种是在其祖先的某一层上破坏了平衡的
7、要求,使整个二叉排序树不再是AVL树。,20,技术课件,最小不平衡子树,处理失去平衡的方法为首先找出最小不平衡子树(指离插入结点最近,且以平衡因子绝对值大于1的结点为根的子树), 在保证排序树性质的前提下,调整最小不平衡子树中各结点的连接关系,以达到新的平衡。,21,技术课件,22,技术课件,AVL树调整平衡的原则,LL型调整 破坏平衡的原因是由于在A的左子女(L)的左子树(L)中插入新结点,使A的平衡因子由 -1变为 -2而失去平衡。,调整不破坏节点间的序关系。 调整不增加子树的高度。,23,技术课件,LL-调整规则,将A的左子女B提升为新二叉树的根;原来的根A连同其右子树向右下旋转成为B的
8、右子树;B的原右子树作为A的左子树。 调整后仍保持二叉排序树的性质,而且整个(子)二叉树的高度与插入前相同,因此不会影响包含它的更大(子)二叉树的平衡。,4,-1,-1,24,技术课件,RR型调整,破坏平衡的原因是由于在A的右子女(R)的右子树(R)中插入结点,使A的平衡因子由1变为2而失去平衡。 调整规则:与LL型的对称。将A的右子女B提升为新二叉树的根;原来的根A连同其左子树向左下旋转成为B的左子树;B的原左子树作为A的右子树。,4,-1,-1,25,技术课件,LR型调整,破坏平衡的原因是由于在A的左子女(L)的右子树(R)中插入结点,使A的平衡因子由1变为2而失去平衡。 若、全为空树,C
9、就是新插入的结点,记为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,-1,0,4,-1,0,LR(L),LR(R),28,技术课件,RL型调整,破坏平衡的原因是由于在A的右子女(R)的左子树(L)中插入结点,使A的平衡因子由1变为2而失去平衡。 调整规则与LR型的对
10、称。设C为A的右子女的左子女,将A的孙子结点C提升为新二叉树的根,原来C的父结点B连同其右子树向右下旋转成为新根C的右子树,C的原右子树成为B的左子树;原来的根A连同其左子树向左下旋转成为新根C的左子树,原来C的左子树成为A的右子树。,29,技术课件,30,技术课件,调整控制在最小不平衡子树内,上述所有的调整操作中,A为根的最小不平衡子树的高度在插入结点之前和调整之后相同,对A为根的子树之外的其它结点的平衡性无影响,调整后二叉排序树成为平衡二叉排序树。,31,技术课件,元素的删除,与二叉排序树中的结点删除类似,首先找到被删除的结点,如果它不是叶结点,也需要根据二叉排序树的要求转换成一个叶结点的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 技术材料 文件 索引 结构 技术 材料
链接地址:https://www.31doc.com/p-10026454.html